# The Little Schemer Chapter 5

## Commandments   ## Selected Portions of Exercises

### rember* (remove all instances of a value)   Ok that makes sense so far. Next line is: Ah of course. So maybe after we check if `car l` is an atom, if that turns out to be the case, we check if it’s `eqan?` to a? Ok they seem to want to use `eq?` even though `eqan?` seems more general. Ok so a is equal to car l, we call `rember*` with `cdr l`? Looks good so far…
Ok then and if `car l` is not an atom, and we know l isn’t null, do we want to call `rember*` with `car (car l)` or something? Cuz we want to get inside these nested structures, right?
No. Just calling `rember*` with `car l` in the place of `l` is fine. That will let us “dig” into the nested structure.

But first, consider, what if `car l` is an atom but it’s not equal to a? Then we want to `cons` `(car l)` together with the result of calling `rember*` on the rest of l. And then finally, if `(car l)` isn’t an atom, we want to call `rember*` both on the first element and on the rest: Oh and we want to `cons` the results of these calls because we want to make sure we capture the structure of the list.

The whole thing: This is a big jump up in complexity from previous stuff.

### insertR* (insert new word to right of every instance of old word) We defined `multiinsertR` in a previous chapter, but that can’t handle nested list structures, which is what we’re working on in this chapter.

`insertR*` builds a lot on `multiinsertR`. The two new things we add are: 1) a check for whether the first element of a list, `car lat` is an atom before we check whether `car lat` is equal to `old`, and 2) an `else` to handle the situation where `car lat` isn’t an atom (in which case we `cons` together the result of calling `insertR*` on the first element of the list and the rest of the list, respectively):

Initially I had the second cond clause as `((atom? lat))`. That was a mistake. That would lead to us “digging down” into the structured list until we hit an atom, at which point we’d be trying to invoke `null?` on an atom: Initially I used lat for the name of the third argument, but we’re not necessarily dealing with a lat here! So I changed that. I think this is a reference to the final `else` in both procedures. If you know the argument’s `car` isn’t an atom, then you know it’s a list. `multirember` doesn’t recur on the `car` cuz it’s assuming a “flat” list with no nesting, so it just needs to move “from left to right” within the list. It doesn’t need to “dig” or “burrow” into nested structures, which is what recurring on `car` does.

### occur* (count occurrences in nested list)

Now they want something that counts the number of occurrences of something within a nested list structure: My answer, which matches theirs besides the name:

### subst* (substitution within a nested list) This is essentially the same as theirs.

### insertL* My attempt to write `insertL*`:

### member* This was the original `member?` function: My attempt at writing `member*`:

They agree.

### leftmost My attempt at writing `leftmost`:

They agree.

### eqlist?

`eqlist` checks if lists are equal: Wasn’t sure how to write this one. Let’s take a peek. Ok. Pretty much what I expected so far. If both lists are null then we return true makes sense. Didn’t expect this next line. Let’s think about it.
Oh, if the first list is null and the first element of the second list is an atom, return false. Makes sense. If you know that both lists aren’t empty, and that the first list is empty and the second list has an element, you know they’re not equal. So by the time we’d get to this line in the procedure, we would know that it’s not the case that both lists are empty, and that it’s not simultaneously the case that the first list is empty and the second list has an atom as the first element.

So now we’re checking if the first list is empty and return false if it is. This handles the case where the first list is empty and the first element of the second list is itself a list.

Now I think I’m starting to understand this bit from the book: The possibilities we’re going to have to deal with are:

L1: Empty. L2: Empty. (return true) L1: Empty. `car` of L2: Atom. (return false) L1: Empty. `car` of l2 is a list. Return false. The next one I guessed before checking:

`car` of L1: Atom. L2: Empty. Return false.

Guessed it correctly as you can see: Ok so, i figured there would be a test involving `eqan` but didn’t really know or predict what shape it would take: So we check that both `car l1` and `car l2` are atoms in the first part of the cond clause, and if that’s true, then we check that `car l1` and `car l2` are equal, and also make a recursive call to `eqlist?` with the rest of the lists. lots of stuff going on in this clause!

The next clause handles the case where `car l1` is an atom and l2 is a list: I think I’m starting to get the idea. Probably worth trying to think about all the possible cases we need to handle at this point. There are nine questions as the book says cuz there are two arguments and three possibilities for each.

• l1 & l2 are empty
• l1 is empty, `(car l2)` is an atom
• l1 is empty, `(car l2)` is a list
• `(car l1)` is an atom, l2 is empty
• `(car l1)` and `(car l2)` are atoms
• `(car l1)` is an atom, `(car l2)` is a list
• `(car l1)` is a list, and l2 is empty (this would be `((null? l2)`).
• `(car l1)` is a list, and `(car l2)` is an atom (this would be `((atom? (car l2))`)
• `(car l1)` is a list, and `(car l2)` is a list (would this be an else clause where you’d recur on both?)

And then let’s think about what we’d want to return in each of these cases:

• If l1 and l2 are empty, we want to return true because the lists being empty means we either got to the end of the lists without returning false (so the lists are the same), or both lists were empty from the start (and thus the same).
• If l1 is empty and `(car l2)` is an atom, that means the first list has reached an empty state while the second list still has an element. Since we should be proceeding through the lists at the same pace, element by element, if one list “runs out” of elements before the other one does, that indicates that the lists are not the same, and so we should return false.
• If l1 is empty and it is neither the case that either l2 is empty nor that `(car l2)` is an atom, then by process of elimination, `(car l2)` must be a list. Assuming our program proceeds through the lists correctly, if one list “runs out” of elements before the other one does, that indicates the lists are not the same, so we should return false in this case.
• If `(car l1)` is an atom and l2 is empty, then, for reasons previously stated, that indicates the lists are not the same, and so we should return false.
• If `(car l1)` is an atom and so is `(car l2)`, then we want to check whether the actual values are the same. If they are then we recursively call `eqlist` with the remainder of the lists.
• If `(car l1)` is an atom and, by process of elimination, `(car l2)` is a list, then that indicates the lists are not the same and we return false.
• If , by process of elimination, we determine that`(car l1)` is a list, and we also determine that`(car l2)` is empty, that indicates that the lists are not the same, and so we should return false.
• If `(car l1)` is a list (by process of elimination) and `(car l2)` is an atom, that indicates the lists are not the same, and so we should return false.
• If `(car l1)` is a list and `(car l2)` is a list, we should recursively call `eqlist` on both those lists in order to determine whether they’re the same list. EDIT: I left out that you should recur on both the first element of the list and the rest of the list.

OK, while I had to read most of the procedure to do so, I seem to have figured out the principle of how the procedure works: Hurrah!

Regarding ordering, the book makes the point that it’s okay to ask `(atom? (car l2))` in the second question because by that point we know the second list can’t be empty. (If we tried to take `car` of an empty list we’d get an error.)  The first three cases are:
– If l1 and l2 are empty,
– If l1 is empty and `(car l2)` is an atom, and
– if l1 is empty, and `(car l2)` is a list

The first case is the one we return true for. In all other cases we’re considering where the first list is empty, we return false. So I think the answer to their question is yes. I’m clearer on the point now. We want to return false for every case where the first list is null and the second list isn’t. If we already know that it’s not the case that the second list is empty, but that the first one is, then we know.. …will always return true because of the first list being empty. And we can return false when this is the case. And therefore between these questions… …we can address the three cases. My attempt:

Mine was close to theirs, but they also consolidated the `((atom? (car l1) #f)` and `((atom? (car l2)) #f)` lines and got rid of the separate `((null? l2) #f)` line: ### equal? Book says to write `equal?`. Wasn’t sure how to proceed so i peeked: Ok that makes sense as a beginning. Let’s think about the cases:

S1: Atom: S2: Atom.
S1: list of s-expressions. S2: Atom.
S1: Atom. S2: List of s-expressions.
S1: List of s-expressions. S2: List of s-expressions.

If both s-expressions are atoms, we want to see if they’re the same somehow. Since they’re atoms, I don’t think we need to worry about checking for anything else in these case, since there’s no rest-of-a-list to check.

This is what I wrote:

And then I peeked at some more of the answer: Ok looks good so far.
If you know that both arguments aren’t atoms, then you know that if one of them is an atom, the other one isn’t, so they aren’t the same. So then you should return false. My attempt at representing this before checking the answer:

And how they did it: I think these are equivalent and so it’s fine. (EDIT: They ultimately simplified this)

If you know that neither of the two arguments is an atom, then they must be lists. We cannot compare lists directly, so we need to evaluate the lists further with a recursive call. My attempt at representing this before checking the answer:

Whoops. For some reason i was assuming we weren’t gonna use `eqlist?`, which we just made, lol. My approach actually produces an error, cuz my procedure can’t handle `null?`. Here’s the correct answer: This is their simplified version, presented later: ### rewriting eqlist? Hey this is kinda like mutual recursion.

So I did this:

I reasoned since `equal?` (or `myequal?`) can handle the cases where two arguments are both atoms or where one is and atom and one isn’t, we could cover all those by just testing to see if `car` of either `l1` or `l2` was an atom, and then invoke `myequal` if either one was true. I thought we should keep the `null?` tests and also keep the part that addresses the case where `car` of both lists are themselves lists. It looks like their procedure might be even simpler than this though so let’s see what they did: So they kept the `null?` tests. But they dropped the part that checks if `car` of a list an atom and then invokes `equal?` if it is. Also, in the `else` clause, they make a call to `equal?` in the first part instead of `eqlist`. Let’s think about this.

If we know that neither list is empty, then we know that the first element in those lists must either be an atom or a list. `equal?` can deal with atoms and lists (the latter by calling `eqlist`). So really, given the existence of `equal?`, the main issue `eqlist?` needs to deal with is whether either list, or both of the lists, is/are null. Once `eqlist?` checks for that, and if that’s not the case, it can send the `car` of those lists to `equal?` to be dealt with. It also recursively calls itself with `cdr` of the lists. I think this makes sense.

### simplifying rember We want to keep the `null?` line. OTOH, since `equal?` can handle both atoms and lists, maybe we just need an else line?
If we know l isn’t null, we know `car l` is gonna grab something and not give an error. `equal?` can handle both atoms and lists. Whenever we find that `s` and `l` match, whether s is an atom or a list, we want to “remove” that from what we return by returning the rest of l. Otherwise, we want to `cons` `(car l)` together with a recursive call to `remeber` with the remainder of the list in order to maintain the recursive structure.

My attempt:

Their version is essentially the same except for the details of how they structured the `cond` clause (I think this is just a stylistic difference):  Oh gp yeah, it’s doing a different thing than it did before.
Oh they ultimately did further simplification: This way of writing stuff is pretty intuitive now from my Simply Scheme work. I find Little Schemer’s way less intuitive. I think part of the reason is I know what the shorter version means and it’s also cleaner, so it seems more organized to me, while the Little Schemer version seems messy. Trying it the Little Schemer way has value though. I’ve been kind of going back and forth.