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

(define p (list 1 2 3 4))
(map inc p)
(map list p)
(define q (map (lambda (k) (lambda (y) (+ y k))) p))
((cadr q) 5)

Exercise

(b2d (list 0 1 1))
write b2d: list<Number> -> Number

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

(accumulate + 0 p)
(sum p)
(accumulate * 1 p)
(accumulate cons null p)
(accumulate (lambda (e s) (and (is-odd e) s)) #t p)
(accumulate (lambda (e s) (and (is-odd e) s)) #t (list 1 3 5))

Exercise

(zip (list 1 2 3) (list 4 5 6))
write zip: list <A>, list<B> -> list <A x B>

Exercise

(addlists (list 1 2 3) (list 4 5 6))
write addlist: list<Number>, list<Number> -> list<Number>
assume lists have same length

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

(define t (list 1 (list 2 3) (list (list 4 5 6) (list 7 8)) 9))

Some functions on tree: write these using map, accumulate and number?

(countleaves t)
(countnodes t)
(enumerate t)
(maptree inc t)
(enumerate (maptree inc t))

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