X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment10.mdwn;h=ba4df372f42db83b4479c27249f32e8882a50ec0;hp=d7e0e235f23cfc93de7d77fa366ccacb57366127;hb=3a24f457b5d8dfe280e95913d3b13d65f31b6fe8;hpb=72cca371a48d35b0177427b35f23ae8cc704fdf2 diff --git a/assignment10.mdwn b/assignment10.mdwn index d7e0e235..ba4df372 100644 --- a/assignment10.mdwn +++ b/assignment10.mdwn @@ -39,15 +39,16 @@ Of course, if you need help or want us to review your efforts, we'll be glad to solution that traverses the tree exactly once, replacing each leaf as soon as you see it? - Consider a variation in which you must replace each leaf with - its number of occurrences in the tree. Is there any way to do - that with a single traversal? - You can assume that the tree is binary, leaf-labeled (no labels on the internal nodes), and that the leafs are, say, chars. - Here is [a hint](/hints/assignment_10_hint). + Here is [a hint](/hints/assignment_10_hint_1). + + Consider a variation in which you must replace each leaf with + its number of occurrences in the tree. Is there any way to do + that with a single traversal? (Here is [a hint](/hints/assignment_10_hint_2).) + 2. Armed with your solution to problem 1, try this: you have as input a leaf-labeled, binary tree whose labels are strings. You also have as input an interpretation function from strings to meanings. Let the meanings of your strings be primitive elements, for instance: @@ -151,7 +152,7 @@ Of course, if you need help or want us to review your efforts, we'll be glad to ((eq? (car lst) before) (insert-co new before after (cdr lst) (lambda (new-lst lefts rights) (k (cons new (cons before new-lst)) (succ lefts) rights)))) ((eq? (car lst) after) - (insert-co new before after (cdr lst) (lambda (new-lst lefts rights) (k (cons (after (cons new new-lst))) lefts (succ rights))))) + (insert-co new before after (cdr lst) (lambda (new-lst lefts rights) (k (cons after (cons new new-lst)) lefts (succ rights))))) (else (insert-co new before after (cdr lst) (lambda (new-lst lefts rights) (k (cons (car lst) new-lst) lefts rights))))))) -->