## Commandments

## Selected Portions of Exercises

### rember-f

How do you write `rember-f`

? My attempt:

1 2 3 4 5 6 7 8 9 |
(define myrember-f (lambda (test? a l) (cond ((null? l)'()) ((test? (car l) a) (cdr l)) (else (cons (car l) (myrember-f test? a l)))))) |

They agreed.

### lambdas

Some work I did to understand this:

This returns a procedure that checks whether an argument *x* is equal to “hat”:

And these pass the arguments “hat” and “cat” to that argument, respectively, returning the appropriate value:

### rewriting rember-f

My answer:

1 2 3 4 5 6 7 8 9 10 |
(define myrember-f (lambda (test?) (lambda (a l) (cond ((null? l)'()) ((test? (car l) a) (cdr l)) (else (cons (car l) ((myrember-f test?) a (cdr l)))))))) |

I had to think about the recursive case, and providing the `test?`

argument to the recursive invocation.

### insertL-f

This was *insertL* from a previous chapter:

1 2 3 4 5 6 7 8 9 10 11 12 |
(define insertL (lambda (new old lat) (cond ((null? lat) '()) (else (cond ((eq? (car lat) old) (cons new lat)) (else (cons (car lat) (insertL new old (cdr lat))))))))) |

Here’s an intermediate version:

1 2 3 4 5 6 7 8 9 10 |
(define myinsertL-f (lambda (test? new old lat) (cond ((null? lat) '()) ((test? (car lat) old) (cons new lat)) (else (cons (car lat) (myinsertL-f test? new old (cdr lat))))))) |

And here is the final version:

1 2 3 4 5 6 7 8 9 10 11 |
(define myinsertL-f (lambda (test?) (lambda (new old l) (cond ((null? l) '()) ((test? (car l) old) (cons new l)) (else (cons (car l) ((myinsertL-f test?) new old (cdr l)))))))) |

Note the two changes: `test?`

is put in a separate lambda, and is also grouped with `myinsertL-f`

in the recursive call.

Theirs is basically the same.

### insertR-f

This was `insertR`

from earlier:

1 2 3 4 5 6 7 8 9 10 |
(define insertR (lambda (new old lat) (cond ((null? lat) '()) (else (cond ((eq? (car lat) old) (cons old (cons new (cdr lat)))) (else (cons (car lat) (insertR new old (cdr lat))))))))) |

And this is my `insertR-f`

:

1 2 3 4 5 6 7 8 9 10 |
(define myinsertR-f (lambda (test?) (lambda (new old l) (cond ((null? l) '()) ((test? (car l) old) (cons old (cons new (cdr l)))) (else (cons (car l) ((myinsertR-f test?) new old (cdr l)))))))) |

They agreed.

### insert-g

My initial attempt:

1 2 3 4 5 6 7 8 9 10 11 |
(define insert-g (lambda (new old l insert) (cond ((null? l) '()) ((equal? (car l) old) (cond ((eq? insert 'l) (cons new (cons old (cdr l)))) (else (cons old (cons new (cdr l)))))) (else (cons (car l) (insert-g new old (cdr l) insert)))))) |

This is what I attempted at this point before reading further:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
(define insertleft (lambda (new old l) (cons new (cons old (cdr l))))) (define insertright (lambda (new old l) (cons old (cons new (cdr l))))) (define myinsert-g (lambda (new old l f) (cond ((null? l) '()) ((equal? (car l) old) (f new old l)) (else (cons (car l) (myinsert-g new old (cdr l) f)))))) |

They take a similar approach to my second one above:

You can solve `insert-g`

the same with their `seqL`

and `seqR`

procedures, the only difference being that you pass in `cdr l`

to the function instead of *l* directly:

1 2 3 4 5 6 7 8 |
(define theirinsert-g (lambda (new old l f) (cond ((null? l) '()) ((equal? (car l) old) (f new old (cdr l))) (else (cons (car l) (theirinsert-g new old (cdr l) f)))))) |

They wind up writing `insert-g`

as an argument of one argument `seq`

which is either `seqL`

or `seqR`

:

1 2 3 4 5 6 7 8 9 10 11 12 13 |
(define theirinsert-g (lambda (f) (lambda (new old l) (cond ((null? l) '()) ((equal? (car l) old) (f new old (cdr l))) (else (cons (car l) ((theirinsert-g f) new old (cdr l)))))))) (define mynewinsertL (theirinsert-g seqL)) |

1 2 3 |
(define mynewinsertR (theirinsert-g seqR)) |

We’re using a function-creating function to define arbitrary functions in terms of that function, which is something we haven’t done before.

Also, since our function-creating function returns a function that itself takes arguments, we don’t need to use a `lambda`

in our definition.

They had a different point in mind:

1 2 3 |
(define mynewerinsertL (theirinsert-g (lambda (new old l) (cons new (cons old l))))) |

Their version works the same.

### subst

1 2 3 4 |
(define seqsubst (lambda (new old l) (cons new l))) |

1 2 3 |
(define mysubst (theirinsert-g seqsubst)) |

### mystery function yyy & seqrem

I’m a bit confused about this. The first thing I’m confused about is what role `seqrem`

is performing exactly. Stuff like `seqL`

actually performed some operation, but looking at it, `seqrem`

just seems to return the list.

Ok thinking about it more, invoking `insert-g`

with `seqrem`

returns a procedure with `seqrem`

in place of `f`

in the body of `insert-g`

. So we have a `seqrem`

function that just returns the list argument its passed whenever the `car l`

is equal to *old*:

1 2 3 4 5 6 7 8 9 10 |
(define insert-g (lambda (f) (lambda (new old l) (cond ((null? l) '()) ((equal? (car l) old) (seqrem new old (cdr l))) (else (cons (car l) ((theirinsert-g seqrem) new old (cdr l)))))))) |

We see `seqrem`

returning the list it’s passed in this trace result:

`seqrem`

is returning **‘(and bacon)** because **sausage** is the value that returns true for the `equal?`

line, and so the list at that point is **‘(sausage and bacon)**, and so the `cdr l`

at that point is **‘(and bacon)**.

The **(and bacon)** value gets the preceding values (excluding the value we want to remove, which is skipped) `cons`

‘ed on to it by the invocations of the procedures at higher levels of the chain of recursive invocations. And thus we get **‘(pizza with and bacon)**.

### atom-to-function

In the context of discussing the `value`

procedure from chapter 6, they ask the following:

My answer:

1 2 3 4 5 6 7 8 |
(define atom-to-function (lambda (x) (cond ((eq? x '+) +) ((eq? x '×) ×) (else ↑)))) |

I initially erred in thinking about this, cuz I wasn’t thinking about what `operator`

would do.

So *nexp* gets passed into `operator`

, which returns the atom `'+`

. That atom gets passed in as the argument to `atom-to-function`

, which returns a function which performs addition.

### multirember-f

My attempt:

1 2 3 4 5 6 7 8 9 10 |
(define multirember-f (lambda (f?) (lambda (a l) (cond ((null? l) '()) ((f? (car l) a) ((multirember-f f?) a (cdr l))) (else (cons (car l) ((multirember-f f?) a (cdr l)))))))) |

Their solution is essentially the same.

1 2 3 |
(define multirember-eq? (multirember-f eq?)) |

### multirember-T

My solution:

1 2 3 4 5 6 7 8 9 |
(define multiremberT (lambda (f? lat) (cond ((null? lat) '()) ((f? (car lat)) (multiremberT f? (cdr lat))) (else (cons (car lat) (multiremberT f? (cdr lat))))))) |

Their version is essentially the same.

### multirember&co

#### Initial Problem

Initially, `null? lat`

is false, so we skip to the next line.

`(eq? (car lat) a)`

is true, so we recursively invoke `multirember&co`

with `'tuna`

as *a*, `()`

(or the current `(cdr lat)`

as *lat*.

`a-friend`

is used by the `lambda`

procedure to generate a new argument which becomes the *col* for the recursive call. This new argument is a function of two arguments which invokes `a-friend`

. The first argument given to `a-friend`

within this function is the `cons`

of `car lat`

(which is currently **tuna**) and the argument *newlat*. The second argument is the argument *seen*.

`null? lat`

is true within the recursive call, so we invoke our *col* procedure – the function of two arguments involving `a-friend`

– on two empty lists. The following represents the operation of the lambda function in the base case:

#### Another Problem

Next problem:

I found a stackoverflow discussion on this procedure which I found helpful. I talked about this a bunch of the video. I found this post, which was linked in the discussion, very helpful, along with the top stackoverflow answer and the one with the flowcharts.

##### Initial Call to multirember&co

*a*: **tuna**

*lat*: **(and tuna)**

*col*: `a-friend`

**(and tuna)** is not null, and `(car lat)`

of it (**and**) isn’t equal to **tuna**, so we go to the `else`

clause. We pass in **‘tuna** as the new *a* and **(tuna)** as the new *lat*, respectively.

As the new *col*, we pass in a procedure. Let’s call this procedure `z1`

. `z1`

`cons`

es **‘and** onto the first argument taken by the procedure, which is *newlat*. The result of this `cons`

ing serves as the first argument to `a-friend`

. The second argument taken by `z1`

, *seen*, is passed to `a-friend`

directly.

1 2 3 4 |
(define z1 (lambda (newlat seen) (a-friend (cons 'and newlat) seen))) |

##### First Recursive Call

*a*: **tuna**

*lat*: **(tuna)**

*col*: `z1`

Within the first recursive call, *lat* is still not null (it’s **(tuna)** now), so we go to the `eq?`

line. `(car lat)`

is `eq?`

to **tuna**, so we make another recursive call. The arguments to this new recursive call will be **tuna** as *a*, the empty list as *lat*, and what we’ll call `z2`

as *col*.

What does `z2`

consist of? A function of two arguments that invokes `z1`

and `cons`

es **tuna** onto *seen*.

1 2 3 4 |
(define z2 (lambda (newlat seen) (z1 newlat (cons 'tuna seen)))) |

##### Second Recursive Call

*a*: **tuna**

*lat*: **‘()**

*col*: `z2`

Within the second recursive call to `multirember&co`

, the *lat* is empty, so the `null? lat`

condition returns true. Since that is the case, we then pass `z2`

two empty lists. This ultimately leads to the procedure returning **#f**, because by the time the arguments we `cons`

values onto get back to `a-friend`

, the second argument is not null:

#### Yet Another Problem

In general, `multirember&co`

works as follows:

– if `car lat`

is equal to the *a*, then `car lat`

gets `cons`

‘ed onto the second argument.

– Otherwise, `car lat`

gets `cons`

‘ed onto the first argument.

This *col* checks the length of the first argument passed to it. Only one of the elements of the *lat* is equal to *a*, so the final arguments being passed to `last-friend`

will be **(strawberries and swordfish)** for the first argument and **(tuna)** for the second argument. So the value returned will be **3**.

They agree. Whew!

### multiinsertLR

My answer:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
(define multiinsertLR (lambda (new oldL oldR lat) (cond ((null? lat) '()) ((eq? (car lat) oldL) (cons new (cons oldL (multiinsertLR new oldL oldR (cdr lat))))) ((eq? (car lat) oldR) (cons oldR (cons new (multiinsertLR new oldL oldR (cdr lat))))) (else (cons (car lat) (multiinsertLR new oldL oldR (cdr lat))))))) |

Question: if *oldL* and *oldR* are the same, should we add *new* on both sides? Apparently the authors don’t think so, cuz their version was essentially the same as mine.

### multiinsertLR&co

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
<br />(define multiinsertLR&co (lambda (new oldL oldR lat col) (cond ((null? lat) (col '() 0 0)) ((eq? (car lat) oldL) (multiinsertLR&co new oldL oldR (cdr lat) (lambda (newlat L R) (col (cons new (cons oldL newlat)) (add1 L) R)))) ((eq? (car lat) oldR) (multiinsertLR&co new oldL oldR (cdr lat) (lambda (newlat L R) (col (cons oldR (cons new newlat)) L (add1 R) )))) (else (cons (car lat) (multiinsertLR&co new oldL oldR (cdr lat) (lambda (newlat L R) (col (cons (car lat) newlat) L R)))))))) |

#### Step 1

*new*: **salty**

*oldL*: **fish**

*oldR*: **chips**

*lat*: **(chips and fish or fish and chips)**

*lat* is not null.

*car lat* is not equal to *oldL*.

It is, however, equal to *oldR*.

We therefore recursively invoke `multiinsertLR&co`

. The procedure we use, which I’ll call `q1`

, is as follows (note that I’m using `list`

as the `col`

function:

1 2 3 4 5 |
(define q1 (lambda (newlat L R) (list (cons 'chips (cons 'salty newlat)) L (add1 R)))) |

If we use `q1`

on the empty list and two 0’s that we get when the *lat* is null we get the following:

A good start!

#### Step 2

*new*: **salty**

*oldL*: **fish**

*oldR*: **chips**

*lat*: ** (and fish or fish and chips)**

*lat* is not null and `(car lat)`

matches neither our *oldL* nor *oldR*. We therefore go to the else and recursively invoke our `multiinsertLR&co`

procedure with the following function serving as `col`

:

1 2 3 4 |
(define q2 (lambda (newlat L R) (q1 (cons 'and newlat) L R))) |

#### Step 3

*new*: **salty**

*oldL*: **fish**

*oldR*: **chips**

*lat*: **(fish or fish and chips)**

*lat* is not null and `(car lat)`

matches *oldL* so we recursively invoke our `multiinsertLR&co`

with the following function serving as `col`

:

1 2 3 4 |
(define q3 (lambda (newlat L R) (q2 (cons 'salty (cons 'fish newlat)) (add1 L) R))) |

#### Step 4

*new*: **salty**

*oldL*: **fish**

*oldR*: **chips**

*lat*: **(or fish and chips)**

*lat* is not null and `car lat`

is not equal to *oldL* or *oldR* so we go to the else clause and recursively invoke `multiinsertLR&co`

with the following function serving as `col`

:

1 2 3 4 |
(define q4 (lambda (newlat L R) (q3 (cons 'and newlat) L R))) |

#### Step 5

*new*: **salty**

*oldL*: **fish**

*oldR*: **chips**

*lat*: **(fish and chips)**

*lat* is not null but is equal to *oldL* so we recursively invoke `multiinsertLR&co`

with the following as the `col`

:

1 2 3 4 |
(define q5 (lambda (newlat L R) (q4 (cons 'salty (cons 'fish newlat)) (add1 L) R))) |

#### Step 6

*new*: **salty**

*oldL*: **fish**

*oldR*: **chips**

*lat*: **(and chips)**

*lat* is not null and `(car lat)`

is not equal to *oldL* or *oldR* so we recursively invoke `multiinsertLR&co`

with the following as the `col`

:

1 2 3 4 |
(define q6 (lambda (newlat L R) (q5 (cons 'and newlat) L R))) |

#### Step 7

*new*: **salty**

*oldL*: **fish**

*oldR*: **chips**

*lat*: **(chips)**

*lat* is not null and `(car lat)`

is equal to *oldR* so we recursively invoke `multininsertLR&co`

with the following as the `col`

:

1 2 3 4 5 |
(define q7 (lambda (newlat L R) (q6 (cons 'chips (cons 'salty newlat)) L (add1 R)))) |

#### Step 8

*new*: **salty**

*oldL*: **fish**

*oldR*: **chips**

*lat*: **()**

*lat* is null so we return the empty list and two 0’s to the last procedure we generated as the `col`

:

🙂

### evens-only*

1 2 3 4 5 6 7 8 9 10 11 12 13 |
(define evens-only* (lambda (l) (cond ((null? l) '()) ((atom? (car l)) (cond ((even? (car l)) (cons (car l) (evens-only* (cdr l)))) (else (evens-only* (cdr l))))) (else (cons (evens-only* (car l)) (evens-only* (cdr l))))))) |

Their version agreed.

### evens-only*&co

See this stackoverflow thread for useful discussion of this procedure. In particular, see this answer and the flowcharts in this answer.

I’m just doing one “branch” or sublist (the **(9 1 2 8)**) but see the stackoverflow and especially the flow charts for full details. After I did the first branch I felt like I got the idea.

This is more or less what the book winds up eventually revealing as the answer:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
<br />(define evens-only*&co (lambda (l col) (cond ((null? l) (col '() 1 0)) ((atom? (car l)) (cond ((even? (car l)) (evens-only*&co (cdr l) (lambda (newl p s) (col (cons (car l) newl) (* (car l) p) s)))) (else (evens-only*&co (cdr l) (lambda (newl p s) (col newl p (+ (car l) s))))))) (else (evens-only*&co (car l) (lambda (newl p s) (evens-only*&co (cdr l) (lambda (dnewl dp ds) (col (cons newl dnewl) (* p dp) (+ s ds)))))))))) |

Initially, the *l* is `((9 1 2 8)( 3 10 ((9 9) 76 2)`

.

*col* is `the-last-friend`

.

*l* is not null and `(car l)`

is not an atom, so we go to our final *else* clause and take the `(car l)`

of the list *l*.

#### Branch 1

##### Step 1

*l* is **((9 1 2 8) 3 10 ((9 9) 7 6) 2)**

*col* is `the-last-friend`

.

the list is not null. `(car l)`

is not an atom. We go to the final `else`

line. Here is a detailed description of what happens there from stackoverflow. Where `(car l)`

is a nested list:

Imagine you have the results from removing, summing and adding the numbers in

`(car l)`

and call these`newl`

,`product`

, and`sum`

; then imagine you have the results from doing the same thing to`(cdr l)`

, and call them`dnewl`

,`dproduct`

and`dsum`

. To your waiting continuation, give the values produced by`cons`

ing`newl`

and`dnewl`

(since we’re producing a list of lists); multiplying together`product`

and`dproduct`

; and adding`sum`

and`dsum`

.

So I’m going to break the `col`

‘s up into named subprocedures again, using a flow chart from stackoverflow as a guide.

`y1`

partially represents what happens in the final else line of `evens-only*&co`

:

1 2 3 4 5 6 7 |
(define y1 (lambda (al ap as) (evens-only*&co '(3 10 ((9 9) 7 6) 2) (lambda (dl dp ds) (the-last-friend (cons al dl)(* ap dp)(+ as ds)) )))) |

To get the correct value for the overall final procedure, we can invoke `y1`

with ** ‘(2 8) 16 10**, which represents the 1) list of even numbers, 2) product of evens, and 3) sum of the odds, for list **(9 1 2 8)**. If we use these values, we get the right answer. The exact mechanism by which we calculated these numbers has not yet been revealed, and we’re just taking them as a given for now (I pulled them from the chart). The actual source of the numbers is invoking `evens-only*&co`

on `(car l)`

, `(car l)`

in this context being **(9 1 2 8)**. So let’s analyze what the result of that would be so we get a better understanding as to what’s going on.

##### Step 2

*l* is **(9 1 2 8)**

*col* is `y1`

*l* is not null.

`(car l)`

is an atom but not even.

So we analyze it under the `else`

clause for when atoms are not even.

`y2`

partially represents what happens in that `else`

clause:

1 2 3 4 |
(define y2 (lambda (newl p s) (y1 newl p (+ 9 s)))) |

Note that, within the lambda, the **9** from *l* is already in the procedure. Where’s it coming from? It’s the `car`

of *l*.

Note that the else clause invokes `evens-only*&co*`

on `(cdr l)`

. We’ll keep recursively invoking that to get more values.

To get the correct final value for the overall procedure, can invoke`y2`

with the list `'(2 8)`

(the list of even numbers from *l*) as the first argument, the number **16** (the product of the even numbers from *l*) as the second argument, and **1** (the first odd number from *l*) as the third argument:

##### Step 3

*l* is **(1 2 8)**

*col* is `y2`

*l* is not null, and `(car l)`

is an atom but not even, so this will be similar to before.

1 2 3 4 |
(define y3 (lambda (newl p s) (y2 newl p (+ 1 s)))) |

The values that generate the correct final output when passed to `y3`

are **‘(2 8) 16 0**:

##### Step 4

*l* is **(2 8)**

*col* is `y3`

*l* is not null and `(car l)`

is even. From stackoverflow:

Imagine that you have the results of removing odd numbers, multiplying evens, and adding odd numbers from the

`cdr`

of the list, and call them`newl`

,`product`

, and`sum`

respectively.`cons`

the head of the list onto`newl`

(since it’s an even number, it should go in the result); multiply`product`

by the head of the list (since we’re calculating product of evens); leave`sum`

alone; and pass these three values to your waiting continuation`col`

.

1 2 3 4 |
(define y4 (lambda (newl p s) (y3 (cons 2 newl)(* 2 p) s))) |

You can see that `y4`

is pulling the `(car l)`

(or **2**) in in a couple of places here – `cons`

ing it onto *newl* and multiplying it by *p*. Once again, in the actual procedure, we’re getting our arguments to the `lambda`

from the result of a recursive call, but we can also invoke `y4`

with those arguments, which are **(8) 8 0**

##### Step 5

*l* is **(8)**

*col* is `y4`

*l* is not null and `(car l)`

is even.

1 2 3 4 |
(define y5 (lambda (newl p s) (y4 (cons 8 newl) (* 8 p) s))) |

To get the correct final values with `y5`

, you invoke it with **‘() 1 0**

##### Step 6

*l* is **()**

*col* is `y5`

`y5`

is null. pass `'() 1 0`

to `y5`

: