blogahige

the little racketeer – 03

Written by

neilcj

in

,

a collection of notes from reading the little schemer but using racket instead

previously: the little racketeer – 02

chapter 03 – cons the Magnificent

This chapter moves on from just asking questions to building lists recursively. In it, we write some procedures to operate on “flat lists” as I call them–lists of atoms. In the previous chapter, the reader is guided to a procedure that asks “is atom a a member of list l?” We recursively search through the list and as soon as we find a in the list, answer “yes!”

In this chapter, we start out with a procedure that asks the same question of each member of the list, but answers with the same list without the (first instance of the) provided atom. We build the return list with cons, and this is where “The Law of Cons” really first shines. If you always provide a list as the second argument to cons, your recursive list-building will usually work on your first attempt.

Since cdr always returns a list, you end up with a pattern:

(cons some_atom (cdr some_list))

The authors formalize this pattern with three new commandments in this chapter. The Second Commandment is simply: use cons to build lists. The Third Commandment is when building lists, describe the first “typical” element of the list, then cons it onto the “natural recursion.” For lists, the natural recursion is cdr. The Fourth Commandment is to always change one element while recurring, to change it towards termination (make it smaller), to test it with the termination condition, and that if that change is cdr, to test termination with null?.

These commandments give us a couple little mental templates for recursively building lists:

(cond
  ((null? l) '())
  (test (cons (typical_element (cdr l))))
  (else recursive_call (cdr l)))

or:

(cond
  ((null? l) '())
  ((test (recursive_call (cdr l)))
  (else (cons typical_element (cdr l))))

The procedures in this chapter do things that have frequent applications in string processing: search, remove, insert, and replace. They start out with operating on just the first instance of a given atom in a given list, and the chapter closes by rewriting the procedures to operate on every instance of the given element in the given list.

next: chapter 04 – numbers games

More posts