CS 37

Clab 9: map and filter

First, do exercises 2.21, 2.23 on pages 106-107. Then, go on to exercises 2.30, 2.31, 2.32 on pages 112-113. You can find them by scrolling down a couple of screens from: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2.2
If necessary review the material on pages 105 and 112. Remember to substitute '() for nil wherever the text uses nil or put (define nil '()) in your definitions window.

Here is the procedure filter from page 115 of the text.

(define filter (lambda (pred? l) (cond ((null? l) '()) ((pred? (car l)) (cons (car l) (filter pred? (cdr l)))) (else (filter pred? (cdr l)))))) Many problems can be thought of effectively as signals going through a cascade of stages. enumerate, map, filter, and accumulate are powerful tools to implement the stages.

Use filter to define a procedure remove-neg that given an input list of integers, returns a list of all the non-negative integers in the input list.

> (remove-neg '(1 -3 4 5 -6 -7)) (1 4 5) Let's look together at some examples of map and flatmap (define (accumulate op initial sequence) (if (null? sequence) initial (op (car sequence) (accumulate op initial (cdr sequence))))) (define (flatmap proc seq) (accumulate append '() (map proc seq))) (define (map proc seq) ;;overriding built-in map (if (null? seq) '() (cons (proc (car seq)) (map proc (cdr seq))))) (define enumerate-interval (lambda (beg end) (cond ((> beg end) '()) (else (cons beg (enumerate-interval (+ beg 1) end)))))) (define make-pairs1 ;; with flatmap and map (lambda (n) (flatmap (lambda (i) (map (lambda (j) (list i j)) (enumerate-interval 1 n))) (enumerate-interval 1 n)))) (define make-pairs2 ;; with 2 maps (lambda (n) (map (lambda (i) (map (lambda (j) (list i j)) (enumerate-interval 1 n))) (enumerate-interval 1 n)))) (define make-pairs3 ;; with 2 flatmaps (lambda (n) (flatmap (lambda (i) (flatmap (lambda (j) (list i j)) (enumerate-interval 1 n))) (enumerate-interval 1 n)))) Consider: > (enumerate-interval 1 3) (1 2 3) > (map (lambda (j) (list 3 j)) (enumerate-interval 1 3)) ((3 1) (3 2) (3 3)) > (flatmap (lambda (j) (list 3 j)) (enumerate-interval 1 3)) (3 1 3 2 3 3) Now try: > (make-pairs1 3) > (make-pairs2 3) > (make-pairs3 3) Think about why the results are different. Any of the outputs could be useful depending on what you want to do. Just be aware that there is a difference between using map and flatmap. > (cons '((3 1) (3 2) (3 3)) '()) (((3 1) (3 2) (3 3))) > (append '((3 1) (3 2) (3 3)) '()) ((3 1) (3 2) (3 3)) > (cons '((2 1) (2 2) (2 3)) '(((3 1) (3 2) (3 3)))) (((2 1) (2 2) (2 3)) ((3 1) (3 2) (3 3))) > (append '((2 1) (2 2) (2 3)) '((3 1) (3 2) (3 3))) ((2 1) (2 2) (2 3) (3 1) (3 2) (3 3))

Let's look at the text's permutations function

(define filter (lambda (pred? l) (cond ((null? l) '()) ((pred? (car l)) (cons (car l) (filter pred? (cdr l)))) (else (filter pred? (cdr l)))))) (define (permutations s) (if (null? s) ; empty set? (list '()) ; sequence containing empty set (flatmap (lambda (x) ; try map instead of flatmap (map (lambda (p) (cons x p)) (permutations (remove x s)))) s))) (define (remove item sequence) (filter (lambda (x) (not (equal? x item))) sequence))

Note that these ideas, especially map, are really used! See: http://en.wikipedia.org/wiki/MapReduce

Now a challange

Finish the 8-queens problem, ex 2.42 page 124-126. You can find it by scrolling up a couple of screens from: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2.4

Solutions for Clab8 functions. Here is some code for deep versions of subst and remove-all: ;; subst* returns a list that substitutes new for old in an arbitrary ;; list, l, of symbols: (define subst* (lambda (old new l) (cond ((null? l) '()) ((list? (car l)) (cons (subst* old new (car l)) (subst* old new (cdr l)))) ((eq? (car l) old) (cons new (subst* old new (cdr l)))) (else (cons (car l) (subst* old new (cdr l))))))) ;; remove-all* removes all occurrences of sym from an arbitrarily ;; nested list: (define remove-all* (lambda (sym l) (cond ((null? l) '()) ((list? (car l)) (cons (remove-all* sym (car l)) (remove-all* sym (cdr l)))) ((eq? (car l) sym) (remove-all* sym (cdr l))) (else (cons (car l) (remove-all* sym (cdr l)))))))

If you have any questions from last clab, begin with it and get your questions answered.

ask any questions you may have.