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 Sept. 24, 2003 16.410/16.413 Even More Scheme 3 Outline ? ? A mix of Scheme- specific 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. ;; 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))))) 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)))))) 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). 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)) 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