# 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))
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
(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