Some limitations of this scheme: there is no easy way to label an inner, branching node (for example with a syntactic category like VP), and there is no way to represent a tree in which a mother node has a single daughter.
- When processing a tree, you can test for whether the tree is a leaf node (that is, contains only a single number), by testing whether the length of the list is 1. This will be your base case for your recursive definitions that work on these trees. (You'll probably want to write a function `leaf?` that compartmentalizes this check.)
+ When processing a tree, you can test for whether the tree is a leaf node (that is, contains only a single number), by testing whether the length of the list is 1. This will be your base case for your recursive definitions that work on these trees. (You'll probably want to write a function `leaf?` that encapsulates this check.)
Your assignment is to write a Lambda Calculus function that expects a tree, encoded in the way just described, as an argument, and returns the sum of its leaves as a result. So for all of the trees listed above, it should return `1 + 2 + 3`, namely `6`. You can use any Lambda Calculus implementation of lists you like.
-
+<a id=fringe></a>
8. The **fringe** of a leaf-labeled tree is the list of values at its leaves, ordered from left-to-right. For example, the fringe of all three trees displayed above is the same list, `[1, 2, 3]`. We are going to return to the question of how to tell whether trees have the same fringe several times this course. We'll discover more interesting and more efficient ways to do it as our conceptual toolboxes get fuller. For now, we're going to explore the straightforward strategy. Write a function that expects a tree as an argument, and returns the list which is its fringe. Next write a function that expects two trees as arguments, converts each of them into their fringes, and then determines whether the two lists so produced are equal. (Convert your `list_equal?` function from last week's homework into the Lambda Calculus for this last step.)