Newsfeed

Oh My Gawd, It’s Full Of Stars

Dealing With Nested Lists

Learned how to deal with nested lists by asking at least 3 questions:

• Is the list null? If so, return the empty element (an empty list if the value of the function is to be a list, or 0 if you’re evaluating to a number)
• Is the first element in the list an atom? – If so, operate on that atom and cons it onto the natural recursion of the function.
• Else, cons the natural recursion of the function of car list onto the natural recursion of the function of cdr list

You can see this pattern in action on rember* which removes any occurrence of a in l regardless of how deep as are hidden in the nested list. (*, or star is added to the function name to denote that it’s recurring on both, car and cdr.)

(with-test
  (def rember* 
    (fn [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))))))

  (is (= (rember* 'cup '()) '()))
  (is (= (rember* 'cup '(coffee)) '(coffee)))
  (is (= (rember* 'cup '(cup)) '()))
  (is (= (rember* 'cup '(coffee cup)) '(coffee)))
  (is (= (rember* 'cup '((cup))) '(())))
  (is (= (rember* 'cup '(coffee (cup) and (another) cup)) '(coffee () and (another))))
  (is (= (rember* 'sauce '(((tomato sauce)) ((bean) sauce) (and ((flying)) sauce))) '(((tomato)) ((bean)) (and ((flying)))))))

The same applies to insertR and insertL* which respectively return a new list with new inserted next to to old in l.

The questions are again:

• null? – return an empty list that can be cons-ed onto from previous calls
• atom? – checks if car l is what we’re looking for and if so, adds a new element
• else – recurs on both car l and cdr l

(with-test
  (def insertR*
    (fn [new old l]
      (cond (null? l) '()
            (atom? (car l)) (cond (eq? (car l) old) (cons old 
                                                          (cons new (insertR* new old 
                                                                              (cdr l))))

                                  :else (cons (car l) 
                                              (insertR* new old 
                                                        (cdr l))))
            :else (cons (insertR* new old (car l))
                        (insertR* new old (cdr l))))))

  (is (= (insertR* 'new 'old '()) '()))
  (is (= (insertR* 'new 'old '(old)) '(old new)))
  (is (= (insertR* 'new 'old '((old))) '((old new))))
  (is (= (insertR* 'new 'old '((these) old ((shoes old) perfume))) '((these) old new ((shoes old new) perfume)))))

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

  (is (= (insertL* 'new 'old '()) '()))
  (is (= (insertL* 'new 'old '(old)) '(new old)))
  (is (= (insertL* 'new 'old '((old))) '((new old))))
  (is (= (insertL* 'new 'old '((these) old ((shoes old) perfume))) '((these) new old ((shoes new old) perfume)))))

Then, the same pattern applies to subst* which substitutes new with old in l

(with-test 
  (def subst*
    (fn [new old l] 
      (cond (null? l) '()
            (atom? (car l)) (cond (eq? (car l) old) (cons new (subst* new old (cdr l)))
                                  :else (cons (car l) (subst* new old (cdr l))))
            :else (cons (subst* new old (car l))
                        (subst* new old (cdr l))))))

  (is (= (subst* 'orange 'banana '()) '()))
  (is (= (subst* 'orange 'banana '(banana)) '(orange)))
  (is (= (subst* 'orange 'banana '((banana))) '((orange))))
  (is (= (subst* 'cup 'mug '((a mug) in the (((kitchen (mug)))))) '((a cup) in the (((kitchen (cup))))))))

Then, member* returns true if a can be found in l, otherwise it returns false:

Note that instead of returning a list on (null l) it returns false which represents that the element couldn’t be found and we’ve reached the end where we can’t look no further.

(with-test
  (def member* 
    (fn [a l] 
      (cond (null? l) false
            (atom? (car l)) (or (eq? (car l) a)
                                (member* a (cdr l)))
            :else (or (member* a (car l))
                      (member* a (cdr l))))))

  (is (= (member* 'foo '()) false))
  (is (= (member* 'foo '(foo)) true))
  (is (= (member* 'foo '(bar)) false))
  (is (= (member* 'foo '((foo))) true))
  (is (= (member* 'foo '((the quick) ((((brown (springy foo)) jumps over)) the dog))))))

Traversing a Tree

A personal favorite of mine is leftmost which returns the left-most element in l. It’s a bit simpler than the functions before. It recurs only on (car l) unless it is an atom:

(with-test
  (def leftmost 
    (fn [l]
      (cond (null? l) nil
            (atom? (car l)) (car l)
            :else (leftmost (car l)))))

  (is (= (leftmost '()) nil))
  (is (= (leftmost '(apple)) 'apple))
  (is (= (leftmost '((apple))) 'apple))
  (is (= (leftmost '(((hot cider) with (green) tea))) 'hot)))

Testing equality

At the end of the chapter, the authors use recurring on a nested list to test for equality of any s-expression:

(with-test
  (def eqlist?
    (fn [l1 l2] 
      (cond (and (null? l1) (null? l2)) true
            (or (null? l1) (null? l2)) false
            :else (and (equal? (car l1) (car l2))
                       (eqlist? (cdr l1) (cdr l2))))))

  (is (= (eqlist? '() '()) true))
  (is (= (eqlist? '() '(foot)) false))
  (is (= (eqlist? '(foot) '()) false))
  (is (= (eqlist? '(foot) '(foot)) true))
  (is (= (eqlist? '(foot rub) '(foot sub)) false))
  (is (= (eqlist? '(strawberry ice cream) '(strawberry ice cream)) true))
  (is (= (eqlist? '(strawberry ice cream) '(strawberry cream ice)) false))
  (is (= (eqlist? '((coffee) (cup)) '((coffee) (cup))) true)))

(with-test
  (def equal? 
    (fn [s1 s2]
      (cond (and (atom? s1) (atom? s2)) (equan? s1 s2)
            (or (atom? s1) (atom? s2)) false
            :else (eqlist? s1 s2))))

  (is (= (equal? 'a 'a) true))
  (is (= (equal? 'a 'b) false))
  (is (= (equal? 'a '(a)) false))
  (is (= (equal? '(a) 'a) false))
  (is (= (equal? '(a) '(a)) true))
  (is (= (equal? '(a) '(b)) false)))

I am starting to realize how great it is to have a set of tests right away with any function definition. Refactoring will be easy and give me confidence that everything still works. Pretty stoked!