The Little Schemer Chapter 7

set?

Based on what they say in the book, I’m guessing that a set is defined as a list of atoms where no atom appears more than once. This includes the empty set.

This was my solution:

This was their solution:

Their way is very similar to mine. The main difference is that I used `occur` for my second line to see whether there was more than 1 occurrence of the first element of the list within the entire list. So with the example `(apple peaches apple plum)`, I’d check if `apple` occurred more than once. Since it does, I return false. With their approach, they check if the first element of the list is a member of the remainder of the list. So with the same example, they’d check if `apple` was a member of `(peaches apple plum)`. Since it is, that indicates there are two copies of `apple`, and so they return false. I think both approaches are fine.

makeset

I tried but made an error:

The output should be

The way I wrote my `member?` line, the first copy of an atom in a list is being thrown out, but I actually want the second copy to be the one that isn’t included.

I figured out how to get the result I wanted with the following approach:

This is similar to the earlier approach in some ways. The key difference is the use of the `rember*` procedure to remove all subsequent instances of an atom from a list.

They want to use `multirember` instead of `rember*`.

With the previous way of solving the problem, we cared whether `car lat` was a member of `cdr lat` because we only wanted to “skip” `cons`ing the first element of the `lat` together with the rest of the list when that first element was in fact a member of the rest of the list. But with `multirember`, we can just call it for each `car lat` recursively. If there are no duplicates, then `multirember` just returns the whole second argument that it’s given. There’s no downside to just using it every time.

subset?

They ask for a procedure that checks whether one set is a subset of another set, and they define that as each element of the first set appearing somewhere in the second set. My solution:

Their shortened version of the procedure was exactly the same:

Next question:

This was my solution:

Their solution was the same.

eqset?

They want you to write `eqset?`. My attempt:

I check if both sets are empty to make sure they have the same number of atoms.
If `car set1` is a member of set2, I recursively call `myeqset?` with the remainder of set1 and a version of set2 with the first instance of the value of set1 removed by `rember`. Otherwise, I return false.

A similar simplification as was used in the `subset` procedure is possible here by using `and`:

I like this approach and find it elegant.

I was not sure quite what they were getting at. It was apparently this:

A shorter version (that they agree with):

intersect?

My attempt:

This was the same as their shorter version.

Their version was the same.

intersect

My attempt:

Their version agrees with mine.

union

Their solution was the same.

mystery function

It returns elements that are unique to set 1. It is very similar to `union`. The base case is different, though. Instead of returning the entirety of set2 like in `union`, this program returns the empty list. Since `xxx` skips over any elements from set1 that appear in set2, and only `cons`es elements onto the new list it builds which appear only in set1 and not in set2, returning the empty list when set1 is null leads to a list being generated of only the items that are unique to set1.

intersectall

Wasn’t sure how to proceed on this one.

Gonna walk through the first example with the lists of letters in order to understand what’s happening here.

So the base case would be when we have one list left, `(e f g h a b)`. That’s when `cdr l-set` would be null. In that case, we return `'(e f g h a b)`.
So one recursive “step up”, we’d find the `intersect` of `(c a d e)` and `(e f g h a b)`, which would be `(a e)`. Then that value would be returned as the result of `intersectall` one further recursive step up, and so we’d then find the `intersect` of `(a b c)` and `(a e)`, which is `(a)`.

a-pair?

Here was my initial mistaken attempt at defining `a-pair?`:

I only caught one of the cases though:

If you give `a-pair?` a single atom (like 3), or the empty list, or an empty nested list `(())`, my version returns an error message, whereas their version appropriately returns false.

One-liners:

rels and fun?

I’m not sure why the example with the question mark added isn’t a `rel`. It seems like it should be considered a `rel`, as it seems like a set of pairs.

Ok I think I figured it out. A rel is a list of pairs that is a set. A set is a list in which no value appears more than once. Since `apples peaches` appears more than once in the list I wasn’t sure about, that list isn’t a rel. A value can appear as part of a pair more than once (for example, the number 4 appearing more than once in a list) and the list can still be a rel, as long as the full entry isn’t duplicated (e.g. as long as `(4 2)` doesn’t appear twice).

a function for our purposes is a rel for which no first value in a pair appears more than once.

My attempt:

They agree.

revrel

Their version was cleaner.

They also did my version, but they maintain that their version is more readable. I agree.

My solution:

Their solution was the same.

fullfun?

So they want you to write `fullfun?`. I discovered that `seconds` was a function while doing this.

They agreed ðŸ™‚

seconds

They want you to define `seconds`.

My approach:

We `cons` the second value of the first pair/sublist onto the value of the recursive call to `myseconds` with the rest of `l`. Then when we get to the case where there’s only one pair left, we get the `cdr (car l)` of that list, which returns the second value as a list. We actually want it as a list so we can `cons` onto it.