summary |
shortlog |
log |
commit | commitdiff |
tree
raw |
patch |
inline | side by side (from parent 1:
372c27c)
Signed-off-by: Jim Pryor <profjim@jimpryor.net>
Similarly, the leaf-labeled tree:
Similarly, the leaf-labeled tree:
/ \
1 2
can be thought of as a data structure of the form:
/ \
1 2
can be thought of as a data structure of the form:
- Node (its_left_subtree, its_right_subtree) | Leaf (its_label)
+ Leaf (its_label) | Non_leaf (its_left_subtree, its_right_subtree)
and that could be implemented in v2 form as:
and that could be implemented in v2 form as:
- the_tree (\left right. node_handler) (\label. lead_handler)
+ the_tree (\left right. non_leaf_handler) (\label. leaf_handler)
And the node-labeled tree:
And the node-labeled tree:
can be thought of as a data structure of the form:
can be thought of as a data structure of the form:
- Node (its_left_subtree, its_label, its_right_subtree) | Leaf
+ Leaf | Non_leaf (its_left_subtree, its_label, its_right_subtree)
and that could be implemented in v2 form as:
and that could be implemented in v2 form as:
- the_tree (\left label right. node_handler) leaf_result
+ the_tree (\left label right. non_leaf_handler) leaf_result
What would correspond to "folding" a function `f` and base value `z` over a
What would correspond to "folding" a function `f` and base value `z` over a
the label of the root (topmost node) of a tree; extracting the left subtree of
a node; and so on.
the label of the root (topmost node) of a tree; extracting the left subtree of
a node; and so on.
- Think about different ways you might implement v3-style trees.
+ Think about different ways you might implement leaf-labeled trees.
If you had one tree and wanted to make a larger tree out of it, adding in a
new element, how would you do that?
If you had one tree and wanted to make a larger tree out of it, adding in a
new element, how would you do that?
you're building pretty "balanced" in this way?
This is a large topic in computer science. There's no need for you to learn
you're building pretty "balanced" in this way?
This is a large topic in computer science. There's no need for you to learn
-any of the various strategies that they've developed for doing this. But
+the various strategies that they've developed for doing this. But
thinking in broad brush-strokes about what strategies might be promising will
help strengthen your understanding of trees, and useful ways to implement them
in a purely functional setting like the lambda calculus.
thinking in broad brush-strokes about what strategies might be promising will
help strengthen your understanding of trees, and useful ways to implement them
in a purely functional setting like the lambda calculus.