入 Even more scheme Greg Sullivan 16410/16.413 September 24, 2003 Scheme Tutor notes In scheme tutor stick to r5rs scheme The Tutor uses SCM, not miT scheme Strategy: click"Check"button on initial code, in order to view test cases pt.24,2003 16410/16413 Even more scheme
Even More Scheme Greg Sullivan 16.410/16.413 September 24, 2003 Sept. 24, 2003 2 Scheme Tutor Notes • In Scheme Tutor, stick to R5RS Scheme. The Tutor uses SCM, not MIT Scheme. • code, in order to view test cases. 16.410/16.413 Even More Scheme Strategy: click “Check” button on initial
Outline 入 Scheme syntax · Procedures A mix of scheme recursion specific details, and Data general programming tutorial lists structures pt.24,2003 6410/16413 Even More scheme Notes Map, reduce, fold-left, fold-right Show emacs info Go over previous problem set pt.24,2003 16410/16413 Even more scheme
Sept. 24, 2003 16.410/16.413 Even More Scheme 3 Outline • • A mix of Schemespecific details, and general programming tutorial Sept. 24, 2003 16.410/16.413 Even More Scheme 4 Notes • • Scheme syntax Procedures – recursion • Data – lists – structures Map, reduce, fold-left, fold-right – Show emacs info Go over previous problem set
PS.3.1.1: List Creation 入 Write a simple Scheme function, fill-list, that takes as parameters an integer, n, (which is greater than or equal to 1)and an element that can be of any type. The function should create a list of length n, with each item in the list being the element. For example, (fill-list 1x)=>(x) (f|ist5×)=>( XXXXX) ( fill-list 2(a b))=>((a b)(a b)) (define (fill-list n elt) 〔if(=n1) (list elt) (cons elt (fill-list (n 1 elt pt.24,2003 6410/16413 Even More scheme Iterative fill-list (define (fill-list n elt) Clet loop ((nn) (out (list elt))) Cloop (-n 1)(cons elt out))))) pt.24,2003 16410/16413 Even more scheme
;; base case ;; otherwise, more than 1 to do … ) Sept. 24, 2003 16.410/16.413 Even More Scheme 5 PS.3.1.1: List Creation Write a simple Scheme function, fill-list, that takes as parameters an integer, n, (which is greater than or equal to 1) and an element that can be of any type. The function should create a list of length n, with each item in the list being the element. For example, (fill-list 1 'x) => (x) (fill-list 5 'x) => (x x x x x) (fill-list 2 '(a b)) => ((a b) (a b)) (define (fill-list n elt) (if (= n 1) )) (list elt) (cons elt Sept. 24, 2003 16.410/16.413 Even More Scheme 6 Iterative fill-list (define (fill-list n elt) (let loop ((n n) (out (list elt))) (if (= n 1) out (fill-list (- n 1) elt)) (loop (- n 1) (cons elt out)))))
PS 3.1.2: Tree Creation Write a simple Scheme function, fill-tree, that takes as parameters an integer depth,(which is greater than or equal to 2 )and an integer, node-index The function should create a binary tree of the specified depth. The format of the tree should be(node-index(left-child right-child), where left-child and right-child may themselves be trees( this is a recursive definition). At the deepest level of the tree, left-child and right-child are just node indices. For example fill-tree21)=>(1(23) ( fill-tree31)=>(1((2(34)(3(45)) ( fill-tree41)=>(1(2(3(45)(4(56))3(4(56)(5(67)) (define (fi1l-tree depth node -index) f depth 1) node-index (list node-index (list (fill-tree(-depth 1)(+ node-index 1)) (fill-tree(depth 1)(+ node-index 2) pt.24,2003 6410/16413 Even More scheme s there an iterative fill-tree? pt.24,2003 16410/16413 Even more scheme
Sept. 24, 2003 16.410/16.413 Even More Scheme 7 PS.3.1.2: Tree Creation Write a simple Scheme function, fill-tree, that takes as parameters an integer, depth, (which is greater than or equal to 2) and an integer, node-index. The tree should be (node-index (left-child right-child)), where left-child and right-child the tree, left-child and right-child are just node indices. For example, (fill-tree 2 1) => (1 (2 3)) (fill-tree 3 1) => (1 ((2 (3 4)) (3 (4 5)))) (fill-tree 4 1) => (1 ((2 ((3 (4 5)) (4 (5 6)))) (3 ((4 (5 6)) (5 (6 7)))))) (define (fill-tree depth node-index) (if (= depth 1) node-index (list node-index Sept. 24, 2003 16.410/16.413 Even More Scheme 8 Is there an iterative fill-tree? function should create a binary tree of the specified depth. The format of the may themselves be trees (this is a recursive definition). At the deepest level of (list (fill-tree (- depth 1) (+ node-index 1)) (fill-tree (- depth 1) (+ node-index 2))))))
PS.3.1.3: Functional Composition Write a simple Scheme program that determines the maximum depth of functional composition of a mathematical expression written in Scheme notation. For (depth (depth(expt X 2))=> 1 (depth(+(expt x 2)(expt y 2))=>2 (depth((expt x 5)(expt ((expt x 2)1)(52))=> 4 (define (depth exp) (if (pair? exp) ( 1 (apply max(map depth exp)) 0 pt.24,2003 6410/16413 Even More scheme PS.3.1. 4: Indexing Trees 入 It would be handy to have a procedure that is analogous to list-ref, but for tr would take a tree and an index, and return the part of the tree(a leaf or a subtree) at that index. For trees, indices will have to be lists of integers. Consider the tree (4 (8910) To select the element 9 out of it, we need to do something like (second(fourth tree)) nstead, we'd prefer to do (tree- ref (list 3 1)tree) (note that were using zero-based indexing as in list-ref, and that the indices come in top-down order; so an index of (3 1)means you should take the fourth branch of the main tree, and then the second branch of that subtree). As another example, the element 6 could be selected by(tree- ref (list 1 11)tree). Also, it,'s okay for the result to be a subtree, rather than a leaf. so( tree- ref (list o)tree) should return(( 2)3) pt.24,2003 16410/16413 Even more scheme
Sept. 24, 2003 16.410/16.413 Even More Scheme 9 PS.3.1.3: Functional Composition Write a simple Scheme program that determines the maximum depth of functional composition of a mathematical expression written in Scheme notation. For example, (depth 'x) => 0 (define (depth exp) (if )) 0 (+ 1 (apply max (map depth exp))) (pair? exp) Sept. 24, 2003 16.410/16.413 Even More Scheme 10 PS.3.1.4: Indexing Trees (((1 2) 3) (4 (5 6)) 7 (8 9 10)) (second (fourth tree)) (tree-ref (list 3 1) tree) result to be a subtree, rather than a leaf. So (tree-ref (list 0) tree) should return ((1 (depth '(expt x 2)) => 1 (depth '(+ (expt x 2) (expt y 2))) => 2 (depth '(/ (expt x 5) (expt (- (expt x 2) 1) (/ 5 2)))) => 4 It would be handy to have a procedure that is analogous to list-ref, but for trees. It would take a tree and an index, and return the part of the tree (a leaf or a subtree) at that index. For trees, indices will have to be lists of integers. Consider the tree To select the element 9 out of it, we need to do something like Instead, we'd prefer to do (note that we're using zero-based indexing, as in list-ref, and that the indices come in top-down order; so an index of (3 1) means you should take the fourth branch of the main tree, and then the second branch of that subtree). As another example, the element 6 could be selected by (tree-ref (list 1 1 1) tree). Also, it's okay for the 2) 3)
Tree-ref 入 (define( tree-ref index tree); index is a list of indices (if (=0(car index) at the right index (if(null?(cdr index)) and were done nesting return element at this point ( tree-ref (cdr index) (car tree)); otherwise go to next level keep indexing at current level (tree-ref (cons((car index)1)(cdr index))(cdr tree)) pt.24,2003 6410/16413 Even More scheme Mapping (map function list) (map f(e1 e2.e3)) >(fe1)(fe2) 5e3 pt.24,2003 16410/16413 Even more scheme
Sept. 24, 2003 16.410/16.413 Even More Scheme 11 Tree-ref (define (tree-ref index tree) ; index is a list of indices (if ;; keep indexing at current level (= 0 (car index)) ; at the right index ; and we're done nesting (car tree) ; return element at this point Sept. 24, 2003 16.410/16.413 Even More Scheme 12 Mapping • (map function list) • (if (null? (cdr index)) (tree-ref (cdr index) (car tree))) ; otherwise go to next level (tree-ref (cons (- (car index) 1) (cdr index)) (cdr tree)))) (map f ‘(e1 e2 … e3)) => ((f e1) (f e2) … (f e3))
Start of search 入 Search-list · Search-tree Search-graph pt.24,2003 6410/16413 Even More scheme The end pt.24,2003 16410/16413 Even more scheme
Sept. 24, 2003 16.410/16.413 Even More Scheme 13 Start of Search • • • Sept. 24, 2003 16.410/16.413 Even More Scheme 14 The End Search-list Search-tree Search-graph
