Frances' Notes for Sept 14

• ==
  • Lisp is cool because you can treat procedures just like anything else. Continuations. Higher order procedures. Comparisson - (sort students birthdate-comparer) birthday-comparer compares two students and returns true or false depending on which date is before the other day.

(lambda (s1 s2)
 (< (bday-of s1) (bday-of s2))) 

• == Procedure: Map ==

  •   (define (map procedure list)
       (if (null? list)
         '()
         (cons (procedure (car list))
           (map procedure (cdr list))))))

    Lists are flowing. Think about the data flowing. Accumlate returns different things depending on what you give it. Map accumulates using cons instead of dropping on teh floor.
  == Trees - 15 minutes ==
  • Abstract Data types so far have all been linear, they could all be portrayed as lines. Not all data is structured that way. Scheme itself is not linear. If I write:

      (3 + ((2 * 6) - 1))
                          +
                         / \
                        3   -
                           / \
                          *   1
                         / \
                        2   6

    You can do calculation on this. You could display it. you could evaluate it. It is a useful representation. Trees are build out of tree nodes. Nodes matter more than trees, because a tree is either a leaf, or a complex tree node. Binary trees have two "children" the "left child" and the "right child". If is a non-binary node, it just has "children". === Tree Collections ===
    • It might be a good idea to implement a tree using a collection. Given any given node, what is the left child, right child? Lisp is not optamized for trees because there is only hte cons cell.
    • In order traversals - Left Child, datum (the node), right child.
    • Pre-order traversal -Lisp like transversal -Datum, left child, right child. (+ 3 (- (* 2 6))). It's reverse polish notation.