Smatchcube's website 🌍


Exercise 2.60

The element-of-set? procedure is exactly the same, though it’s obviously performing worse if there are duplicates in the list.

The adjoin-set procedure doesn’t have to check if the element is already in the list so the number of steps required by adjoin-set is simply \((1)\), with the previous representation the order of growth was \((n)\).

The union-set procedure is also straightforward, as adjoin-set the order of growth is \((1)\) which is way better than the growth with the previous representation which was \((n^2)\).

For the intersection-set procedure we need to at least check if the elements are in both sets so we need to do a element-of-set? check for each element of set2, hence with this representation the intersection-set procedure is also \((n^2)\). I have transformed the procedure to be iterative so the procedure is now \((1)\) in space compared to \((n)\) in the previous procedure with \(n\) the number of elements in the intersection (because the old procedure used cons recursively).

Even if it’s faster to compute adjoin-set and union-set with this representation I can’t really think of applications for which the duplicate representation is better. It may be useful if we are dealing with a lot of union and adjoin operations but that’s it. The non-duplicate version is better when dealing with cardinals of sets.