a collection of notes from reading the little schemer but using racket instead
Chapter 05 – *Oh My Gawd*: It’s Full of Stars
The first part of this chapter introduces us to the concept of recurring through deeper lists by iterating on the previously written procedure rember, which removed instances of a given atom from a list, but only worked on what I call “flat lists” (lists which contain only atoms). They prompt with a scaffold after two examples, about which I have a little extended discussion.
With this one, I noticed my solutions are starting to differ more from the text. In this example, the text uses a nested cond block:
(define rember*
(lambda (a l)
(cond
((null? l) '())
((atom? (car l)
(cond
((eq? (car l) a)
(rember* a (cdr l)))
(else (cons (car l)
(rember* a (cdr l))))))
(else (cons (rember* a (car l))
(rember* a (cdr l)))))))My solution
(define myrember*
(λ (a l)
(cond
((null? l) '())
((list? (car l))
(cons (myrember* a (car l))
(myrember* a (cdr l))))
((eq? a (car l)) (myrember* a (cdr l)))
(else (cons (car l) (myrember* a (cdr l)))))))null? is a terminating condition, so test that first. then testing if the first element of l is itself says if it is, basically recur through that sub-list and combine the results with (cdr l), but if (car l) is not a list or null, then it is atomic (if the input follows The Law of Cons), so we can remove that if it is equal to a. Finally else leads to the natural recursion. No need for nested cond blocks.
Since the text uses atom? and I used list?, I thought that my solution might not be correct. I wrote a little test to see how myrember* and rember* deal with non-list pairs. It turns that that either procedure works for the examples in the text, and both fail if you put a non-list pair inside l because both procedures assume that (cdr l) is always a list in the recursive calls of myrember*/rember*.
📌When is a pair that is not a list useful?
Non-list pairs are used intentionally, sometimes. For example, the make-hash function takes a list of pairs, where the car of each pair is a key and the cdr is an arbitrary value.
The Racket Guide: 2.4 Pairs, Lists, and Racket Syntax
This chapter “finalizes” the First Commandment:
When recurring on a list of atoms, lat, ask two questions about it: (null? lat) and else.
When recurring on a number, n, ask two questions: (zero? n) and else.
When recurring on a list of S-expressions, l, ask three questions: (null? l), (atom? (car l)), and else.
My intuition leads me to ask (list? l). Is there a good reason not to?
The Fifth Commandment is finalized as:
Always change at least one argument while recurring. When recurring on a list of atoms, lat, use (cdr lat). When recurring on a number, n, use (sub1 n). And when recurring on a list of S-expressions, l, use (car l) and (cdr l) if neither (null? l) or (atom? (car l)) are true.
It must be changed to be closer to termination. The changing argument must be tested in the termination condition:
When using cdr, test termination with null? and when using sub1, test termination with zero?.
Finally, we get a Sixth Commandment warning us against premature optimization:
Simplify only after the function is correct.
The remaining procedures in the chapter are straightforward adaptations of older procedures into versions that accept lists of S-expressions, but repetition is good for the brain.