Recitation 6

Today's ideas: List Functionals, Trees

Last time we talked about lists and saw map, a standard functional (ie, higher order function) on lists. This time we played with some more list functionals, and then moved onto to similar operations on trees.

Map: the easiest list functional

Type of map is (A -> B), list<A> -> list<B>

Examples

Exercise We could have written these all recursively: they would all have looked like map. So map can be viewed as a pattern that we're exploiting. We don't have to think about recursion when we use map.

Accumulate: another basic list functional

Also called reduce or fold

Examples

Exercise Exercise We discussed how zip makes a list of pairs, not a list of lists.
We could have written these all recursively: they would all have looked like accumulate. So accumulate can be viewed as a pattern, like map.

Trees

A simple kind of tree with numbers at leaves only.

Type definition:
    Tree = Number | List<Tree>

Example

Some functions on tree: write these using map, accumulate and number? We discussed the similarity between countleaves and countnodes.

Puzzle: how to implement a function that applies maptree then enumerate without using maptree?


Definitions assumed


(define (inc i) (+ i 1))
(define (dec i) (- i 1))
(define (is-odd n)
                   (cond ((= n 0) #f)
                         ((= n 1) #t)
                         (else (is-odd (- n 2)))))

(define (map f p)
  (if (null? p)
      p
      (cons (f (car p)) (map f (cdr p)))))

(define (accumulate f base p)
    (cond
      ((null? p) base)
      (else (f (car p) (accumulate f base (cdr p))))))
 

Definitions we wrote

(define (sum p) (accumulate + 0 p))

;; converts binary (represented as list, backwards) to decimal -- eg, (0 1 1) to 6
(define (b2d p)
  (accumulate (lambda (e s) (+ e (* s 2))) 0 p))

(define (zip p q)
  (if (null? p)
      p
      (cons (cons (car p) (car q))
            (zip (cdr p) (cdr q)))))

;; sums two lists elementwise
(define (addlists p q)
  (map (lambda (c) (+ (car c) (cdr c))) (zip p q)))

(define (countleaves t)
  (if (number? t)
      1
      (sum (map countleaves t))))

(define (countnodes t)
  (if (number? t)
      1
      (inc (sum (map countnodes t)))))

;; flatten for a tree: returns list of leaves
(define (enumerate t)
  (if (number? t)
      (list t)
      (accumulate append null(map enumerate t))))

;; map over a tree
(define (maptree f t)
  (if (number? t)
      (f t)
      (map (lambda (t) (maptree f t)) t)))



Daniel Jackson
Sept 23, 1999