Newsfeed

Cons the magnificent

In this chapter I learned how to create lists using cons and recursion.

The first function discussed was rember, which removes the first occurrence of a in lat and returns the result as a new list.

As you can see from below, the function asks three questions:

1. Is lat null?, or empty. If so, return the empty list `()
2. Is (car lat) equal to the atom we’re looking to drop? If so, return the rest of the list (cdr lat) and effectively drop (car lat) from the list, implementing the requirement of “remove member”.
3. If neither of the above is true, (cons (car lat)) onto the natural recursion of rember with a and the rest of lat, which is (cdr lat).

*Note that I am using cones in my listings to stay consistent with the book.

(with-test
  (def rember 
    (fn [a lat] 
      (cond (null? lat) '()
            (eq? (car lat) a) (cdr lat)
            :else (conss (car lat) (rember a 
                                           (cdr lat))))))

  (is (= (rember 'and '()) '()))
  (is (= (rember 'and '(and)) '()))
  (is (= (rember 'and '(bacon lettuce and tomato)) '(bacon lettuce tomato)))
  (is (= (rember 'mint '(lamb chops and mint jelly)) '(lamb chops and jelly)))
  (is (= (rember 'mint '(lamb chops and mint flavored mint jelly)) '(lamb chops and flavored mint jelly))))

I have begun to always start my tests with the null-case, here it’s…

(is (= (rember 'and '()) '()))

…which drives out the question #1.

Then I write the minimal test that drives out the main behavior without the need for recursion…

(is (= (rember 'and '(and)) '()))

…which drives out the question #2

And then finally I write a test that drives out question #3 such as…

(is (= (rember 'and '(bacon lettuce and tomato)) '(bacon lettuce tomato)))

As the books describes in the beginning, over time, patterns emerge from this simple example.

The second function I learned was firsts which takes the first s-expression of each nested list in the list.

This time there are only two questions we ask: 1. Is the list null?, then return the empty list (). This is the necessary terminal clause that will cause a recursion to stop. 2. Else,(cons (car (car l))onto the natural recursion offirstswith(cdr l)`.

So, for example (firsts '((a b) (c d) (e f))) evaluates to (a c e).

Here, again, I started with the simplest case with '() for l and worked through the rest of the example step by step following the book.

(with-test
  (def firsts 
    (fn [l]
      (cond (null? l) '()
            :else (cons (car (car l))
                        (firsts (cdr l))))))

  (is (= (firsts '()) '()))
  (is (= (firsts '((apple peach pumpkin)
                   (plum pear cherry)
                   (grape raisin pea)
                   (bean carrot eggplant)))
         '(apple plum grape bean)))
  (is (= (firsts '((a b) (c d) (e f)))
         '(a c e)))
  (is (= (firsts '((five plums)
                   (four)
                   (eleven green oranges)))
         '(five four eleven)))
  (is (= (firsts '(((five plums) four)
                   (eleven green oranges)
                   ((no) more)))
         '((five plums)
           eleven
           (no)))))

After that I wrote insertR which inserts a new s-expression to the right of an the first occurrence of an existing s-expression inside a list.

The questions this function needs to ask and answer are:

1. Is lat null? If so, return the empty list `().
2. Is (car lat) equal to old and if so, (cons old (cons new (cdr lat))) which basically says append new, then old onto the rest.
3. Else (cons (car lat)) onto the natural recursion of this function with new, old and (cdr lat).

(with-test
  (def insertR 
    (fn [new old lat]
      (cond (null? lat) '()
            (eq? (car lat) old) (cons old
                                      (cons new (cdr lat)))
            :else (cons (car lat)
                        (insertR new old 
                                 (cdr lat))))))

  (is (= (insertR 'topping 'fudge '())
         '()))
  (is (= (insertR 'topping 'fudge '(ice cream with fudge for dessert))
         '(ice cream with fudge topping for dessert)))
  (is (= (insertR 'jalapeno 'and '(tacos tamales and salsa))
         '(tacos tamales and jalapeno salsa)))
  (is (= (insertR 'e 'd '(a b c d f g d h))
         '(a b c d e f g d h))))

Now, the next function, insertL inserts a new element to the left of an existing one. The only difference here was what we do in case (eq? (car lat) old) namely (cons new lat)

(with-test
  (def insertL
    (fn [new old lat]
      (cond (null? lat) '()
            (eq? (car lat) old) (conss new lat)
            :else (cons (car lat) (insertL new old (cdr lat))))))

  (is (= (insertL 'topping 'fudge '())
         '()))
  (is (= (insertL 'topping 'fudge '(ice cream with fudge for dessert))
         '(ice cream with topping fudge for dessert))))

Now up to this point the functions only replace or insert or remove the first occurence of whatever the matching function was. What about multiple occurrences and manipulations?

When you look at multimember you’ll notice that we drop the current occurrence of a in lat and recur via (multirember a (cdr lat) which will drop any following occurrences as well.

(with-test
  (def multirember 
    (fn [a lat]
      (cond (null? lat) '()
            (eq? (car lat) a) (multirember a (cdr lat))
            :else (conss (car lat) (multirember a (cdr lat))))))
  (is (= (multirember 'cup '())
         '()))
  (is (= (multirember 'cup '(coffee cup tea cup and hick cup))
         '(coffee tea and hick))))

This pattern persisted for the following, improved versions of insertL, insertR and subst:

(with-test
  (def multiinsertR
    (fn [new old lat]
      (cond (null? lat) '()
            (eq? (car lat) old) (conss old (conss new (multiinsertR new old (cdr lat))))
            :else (conss (car lat) (multiinsertR new old (cdr lat))))))

  (is (= (multiinsertR 'new 'old '())
         '()))
  (is (= (multiinsertR 'new 'old '(old socks old beer))
         '(old new socks old new beer))))

(with-test
  (def multiinsertL
    (fn [new old lat]
      (cond (null? lat) '()
            (eq? (car lat) old) (conss new (conss old (multiinsertL new old (cdr lat))))
            :else (cons (car lat) (multiinsertL new old (cdr lat))))))

  (is (= (multiinsertL 'new 'old '())
         '()))
  (is (= (multiinsertL 'new 'old '(old socks old beer))
         '(new old socks new old beer))))

(with-test
  (def multisubst
    (fn [new old lat]
      (cond (null? lat) '()
            (eq? (car lat) old) (conss new (multisubst new old (cdr lat)))
            :else (conss (car lat) (multisubst new old (cdr lat))))))
  (is (= (multisubst 'new 'old '())
         '()))
  (is (= (multisubst 'new 'old '(frog))
         '(frog)))
  (is (= (multisubst 'new 'old '(old))
         '(new)))
  (is (= (multisubst 'new 'old '(old old old))
         '(new new new))))

All in all I had great fun really digging into it. The question/answer style still lends itself to writing the test first and then following along with the implementation.