I am almost through with The Little Schemer. I got through the first seven chapters fairly quickly. There are no exercises per se. They will ask questions, invite you to figure out the answer, and show you. I admit, a few times I peeked, but only after trying to get it myself.
There were a few things in chapter 8 that were mind-bending. One was using higher-order functions for code-reuse.
In chapter 3, the authors introduce a few functions. One is “rember”, which removes an element (or member) from a list:
(runit:check-equal? (lt-sc:rember 'and '(bacon lettuce and tomato))
'(bacon lettuce tomato))
Another is “insertR”, which inserts a new element to the right of an old element in a list:
(runit:check-equal? (lt-sc:insertR 'topping
'fudge
'(ice cream with fudge for dessert))
'(ice cream with fudge topping for dessert))
The third is “insertL”, which inserts a new element to the left of an old element:
(runit:check-equal? (lt-sc:insertL 'topping
'fudge
'(ice cream with fudge for dessert))
'(ice cream with topping fudge for dessert))
The functions are pretty much identical. In chapter 8, they make a base function, and then make three more to cover the three different requirements.
(define insert-g
(lambda (seq)
(lambda (new old l)
(cond [(null? l) (quote ())]
; calling passed seq function
[(eq? (car l) old) (seq new old (cdr l))]
[else (cons (car l) ((insert-g seq) new old (cdr l)))]))))
(define insertL2
(insert-g (lambda (new old l)
(cons new (cons old l)))))
It works just like the original:
(runit:check-equal? (lt-sc:insertL2 'topping
'fudge
'(ice cream with fudge for dessert))
'(ice cream with topping fudge for dessert))
This reminds me of something that Eric Normand showed in Purely Functional, where he puts anonymous functions in the values of a map. I wrote about that in August of 2018.
The truly mind-bending part was the “collectors”. Dark arts, these are.
They define a function that does the usual removing of members. It takes an additional parameter which is a function that does some calculations/manipulations on the resulting list. But in the recursive calls, the function uses inline lambdas to make additional collections.
Here is their explanation from page 140; the function is (multirember&co a lat f), where “a” is an atom, “lat” is a list of atoms, and “f’ is a function: It looks at every atom of the lat to see whether it is eq? to a. Those atoms that are not are collected in one list ls1 ; the others for which the answer is true are collected in a second list ls2 . Finally, it determines the value of (f ls1 ls2 ).
Here is the multirember&co function:
(define (multirember&co a lat col)
(cond [(null? lat) (col '() '())]
[(eq? (car lat) a)
(multirember&co a (cdr lat)
(lambda (newlat seen)
(col newlat
(cons (car lat) seen))))]
[else
(multirember&co a (cdr lat)
(lambda (newlat seen)
(col (cons (car lat) newlat)
seen)))]))
Here is the function we will use in our test:
(define (last-friend x y) (length x))
The second argument is unused in last-friend. So when you use last-friend, it will count how many elements are not equal to the first argument. If it returned the length of y, it would tell us how many times the first argument is in the list.
Here are the tests in Racket:
(runit:check-equal? (lt-sc:multirember&co 'tuna
'(strawberries tuna and swordfish)
lt-sc:last-friend)
3)
(runit:check-equal? (lt-sc:multirember&co 'tuna
'(strawberries tuna swordfish tuna shark)
lt-sc:last-friend)
3)
Later, they use collectors on functions that work on multi-level lists. There is a recursive call within the collector.
I think I understand this, but I am not entirely sure about it. I was able to figure out some of the collector examples as they went along. Truly this is unholy power.
You’re welcome.
Image from Corpus Agrimensorum Romanorum, a 6th century manuscript on land surveying housed at the Herzog August Library in Wolfenbüttel. According to Wikipedia, “It is one of the few surviving non-literary and non-religious illuminated manuscripts from late antiquity.” This image is assumed to be allowed under Fair Use.