CS 22

Clab 11: Representing sets by unordered and ordered flat lists

I'll say a few words about the 8-queens challange.

Take a look at my solutions to the exercises from clab10 (below). Make sure you understand them. If you don't, ask me for an explanation. Then, do the following exercises for sets. Note that for all but the last one, the list representing a set contains unique elements (no repeats).

  1. exercise 2.59 on page 153
  2. exercise 2.61 on page 155
  3. exercise 2.62 on page 155
  4. exercise 2.60 on page 153
On line a couple of screens down from: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-16.html#%_sec_2.3.3

Solutions to the exercises from clab10.

2.30, (define square (lambda (x) (* x x))) (define square-tree ;;directly w.o. higher order procedures (lambda (tree) (cond ((null? tree) '()) ((not (pair? tree)) (square tree)) (else (cons (square-tree (car tree)) (square-tree (cdr tree))))))) (define (map proc items) (if (null? items) '() (cons (proc (car items)) (map proc (cdr items))))) (define square-tre2 ;;; using map (lambda (tree) (map (lambda (subtree) (cond ((pair? subtree) (square-tre2 subtree)) (else (square subtree)))) tree))) 2.31, (define tree-map (lambda (funct tree) (cond ((null? tree) '()) ((not (pair? tree)) (funct tree)) (else (cons (tree-map funct (car tree)) (tree-map funct (cdr tree))))))) 2.32 (define (subsets s) (if (null? s) (list '()) (let ((rest (subsets (cdr s)))) (append rest (map (lambda (sub) (cons (car s) sub)) rest)))))

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

Here is remove-neg.

(define remove-neg (lambda (lis) (filter (lambda (x) (>= x 0)) lis)))

ask any questions you may have.