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*.

They also made things shorter:

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” consing 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:

They had a different approach:

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

My answer:

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 conses 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 of pair functions

One-liners:


My answer:

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.

Leave a Reply

Your email address will not be published.