Due: Thursday, Feburary 14, 11:59pm via turnin (assignment
name hwk5)
Collaboration Policy:
Pairs Permitted
This assignment lets you try programming with continuations. Get as far as you can with them. Showing that you are learning to think with continuations will get you most of the point (and points) of these problems.
The fringe of a tree is the sequence of values at its leaves encountered via inorder traversal. For example, the fringe of the following tree is 1,2,3,4,5.
o
/ \
1 o
/| \
2 | 5
o
/ \
3 4
Given two (n-ary) trees, we can ask whether their fringes are the same (as a sequence, not as a set). One easy way to do this is to build the list for each fringe, then walk the lists to check whether they are the same. Could you do this without creating intermediate data structures (such as the lists) though? In other words, could you do this purely through clever handling of the control flow?
Write a program same-fringe that takes two trees
and determines whether their fringes are the same without creating any
new explicit data structures (ie, use continuations to jump back and
forth between the two trees). Represent your trees using nested
Scheme lists. For example, the tree above would be written as
(list 1 (list 2 (list 3 4) 5)).
The coroutines code we developed in class had some limitations, including:
Modify the code to address the first problem, and optionally the second. Include a comment explaining why the infinite loop occurs. Also include comments explaining your solution(s).
Submit a single file with your work for this assignment. Make sure your name is at the top of your file (in a comment).
Nothing yet ...