Some More Scheme Greg Sullivan 16.410/16.413 September 17, 2004 Sept. 17, 2003 2 Outline ? A mix of Scheme- specific details, and general programming tutorial Procedures – recursion – lists – structures ? Scheme syntax 16.410/16.413 More Scheme ?Data Sept. 17, 2003 3 Pairs, Lists ? ? (cons 1 (cons 2 ())) ? (list 1 2) ) ? (pair? (cons 1 2)) (pair? (list 1 2 3)) => #t ? (list? (cons 1 2) => #f (list? (cons 1 ‘())) => #t 1 2 car 2 () car 1 car Sept. 17, 2003 4 Sum a list ? Assuming list is a flat list of numbers, return sum. (define (sum l) …) ?1 st (define (sum l) (if (null? l) 0 1 2 cdr cdrcdr solution – use recursion. (+ (car l) (sum (cdr l))))) (cons 1 2) => (1 . 2) ?() ?‘( 16.410/16.413 More Scheme 16.410/16.413 More Scheme Sept. 17, 2003 5 Sum list, iterative version ? (define (sum l) (let loop ((l l) (answer 0)) (if (null? l) answer Sept. 17, 2003 6 How about list product? ? ? (fold operator initial-value list) (fold + 0 ‘(1 2 3 4)) = 10 (define (fold op initial l) (if (null? l) initial (define (list-product l) (fold * 1 l)) (define (factorial n) …) (define (factorial n) Now construct an iterative version (loop (cdr l) (+ answer (car l)))))) Abstract from list sum. (op (car l) (fold op initial (cdr l))))) … fold … first-n (fold * 1 (first-n n))) 16.410/16.413 More Scheme 16.410/16.413 More Scheme Sept. 17, 2003 7 Trees ? – Tree<C> = List<Tree<C>> | Leaf<C> – Leaf<C> = C ? – leaf? 2 4 6 8 2 6 8 4 root children or subtrees Sept. 17, 2003 8 countleaves – – – Implementation: ;base case ((leaf? tree) 1) ;base case (else ;recursive case (define (leaf? x) (not (pair? x))) Type Definition: Operations: ? Strategy base case: count of an empty tree is 0 base case: count of a leaf is 1 recursive strategy: the count of a tree is the sum of the countleaves of each child in the tree. (define (countleaves tree) (cond ((null? tree) 0) (+ (countleaves (car tree)) (countleaves (cdr tree)))))) 16.410/16.413 More Scheme 16.410/16.413 More Scheme Sept. 17, 2003 9 The End Still to come: ? ? Sept. 17, 2003 10 car car car car Structures / Records Exceptions (continuations) cdr cdr cdr cdr 16.410/16.413 More Scheme ?Macros 16.410/16.413 More Scheme Sept. 17, 2003 11 list-ref ? ; return nth, 0-based, element of l ; #f if n > (length l) (define (list-ref l n) … ) (define (list-ref l n) (cond ((null? l) #f) ((= 0 n) (car l)) (else Sept. 17, 2003 12 The Define special form ? (define <name> <value expression>) – – – (define pi 3.14) e v a l d e f i n e -r u l e p r i n t scheme versions differ ? world ? world "pi --> 3.14" undefined name pi 3.14 Environment define-rule: name in 1st operand position is bound to that value. returned value of the define expression is undefined visible execution value 16.410/16.413 More Scheme (list-ref (cdr l) (- n 1))))) 16.410/16.413 More Scheme evaluate 2nd operand only, returning a value.