入 Some more scheme Greg Sullivan 16410/16.413 September 17, 2004 Outline Scheme syntax · Procedures A mix of scheme recursion specific details, and Data general programming tutoria lists structures sept.17,2003 16.410/16. More Scheme
Some More Scheme Greg Sullivan 16.410/16.413 September 17, 2004 Sept. 17, 2003 2 Outline • A mix of Schemespecific details, and general programming tutorial Procedures – recursion – lists – structures • Scheme syntax 16.410/16.413 More Scheme • Data
Pairs. Lists 入 (cons12)=>(1.2) car cdr (cons 1(cons 2 0) (list 1 2) (pair?(cons 1 2))(pair?(list 1 2 3)=>#t (list?(cons 1 2)=>#f (list?(cons 10)=> sept.17,2003 16.410/16. More Scheme Sum a list Assuming list is a flat list of numbers return sum.(define(sum I)...) 1st solution -use recursion (define(sum I) (if (null? D) 0 (+(car D)(sum(cdr D ) sept.17,2003 16.410/16. More Scheme
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) …) • 1st (define (sum l) (if (null? l) 0 1 2 cdr cdr cdr 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
Sum list, iterative version 入 Now construct an iterative version (define(sum D) (let loop(( D)(answer o) (if (null? D) answer (loop (cdr D)(+ answer(car sept.17,2003 16.410/16. More Scheme How about list product? Abstract from list sum (define(factorial n) fold .. first-n fold operator initial-value list)L-) (fod+0(1234)=10 (define(factorial n) (define(fold op initial D) (fold *1(first-n n) (if (null? D) initial (op(car I)(fold op initial (cdr D)) (define(list-product D)(fold*1 D) sept.17,2003 16.410/16. 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
rees children or 平中 入 subtrees 2 Type Definition Tree= List>I Leaf Operations leaf? sept.17,2003 16.410/16. More Scheme countleaves Strateg 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 Implementation (define (countleaves (cond ((null? tree) base case ((leaf? tree)1) base case curs工 ve case (+ (countleaves (car tree)) (countleaves (cdr tree)))))) (define (leaf? x) (not (pair? x))) sept.17,2003 16.410/16. More Scheme
Sept. 17, 2003 7 Trees • – Tree = List> | Leaf – Leaf = 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
入 The end Still to come · Structures/ Records Exceptions(continuations) · Macros sept.17,2003 16.410/16. More Scheme d sept.17,2003 16.410/16. 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
list-ref 入 return nth. 0-based. element of l #f if n>(length D) ( define( list-ref i n)…) (define (list-ref I n) cond ((null? D) (=0n) (car D) (else (list-ref (cdr D)(n 1)) sept.17,2003 16.410/16. More Scheme The define special form define-rule: (define ) evaluate 2nd operand only, returning a value name in 1st operand position is bound to that value visible scheme versions differ world (define pi 3.14) P-->3.14 Environment executio name value world undefined 3.14 sept.17,2003 16.410/16. 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 ) – – – (define pi 3.14) eval define-rule print 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