First, some pointers about what isn't quite in order in your attempt.
- The base case of your
treefold
function matches against the value constructor Empty
, but you don't define the bin_tree
datatype to include an Empty
value constructor.
- As John Coleman points out in his comments, you've defined the
Node
value constructor to take a pair, but in your recursive case you match Node
with a triple. Bearing in mind Simon Shine's excellent answer explaining folds over binary trees, we can probably infer the reason for this: your treefold
function expects a canonical binary tree (where each node has a value and two branches) but the data structure you defined doesn't implement this structure. I'm not sure what the data structure you've defined is called, despite giving it a good google (though I think I've implemented it before!).
- You apply
g
to z
twice, once down the left branch and once down the right branch. This would mean the value passed in to that place will get included in the fold twice for every branch. I don't imagine that's what you intended.
(1) and (2) should both be caught by the type checker as soon as you try to compile or load your code. You should try this, if you haven't already, and make sure you understand the feedback the type checker provides. It is a very valuable tool.
(3) has to do with the nature of the function you intend to write, and it is only out of order if you didn't mean it.
Here's one way to define a fold over the data structure you defined.
structure Tree =
struct
datatype 'a tree = Leaf of 'a
| Node of 'a tree * 'a tree
fun foldl f x t =
case t
of Leaf y => f (x, y) (* The base case *)
| Node (treeL, treeR) =>
let
val l = foldl f x treeL (* Recurse down the left branch *)
in
foldl f l treeR (* Recurse down the right branch *)
end
end
Notice that, having put foldl
here in the Tree
module, we now how have a function that mirrors the foldl
function in the List
structure (and elsewhere):
- List.foldl;
val it = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
- Tree.foldl;
val it = fn : ('a * 'b -> 'a) -> 'a -> 'b bin_tree -> 'a
This would make it easier to parameterize over either lists or trees.
It works like so:
- foldl op+ 0 (Node (Leaf 3, Node (Node (Leaf 1, Leaf 2), Leaf 5)));
val it = 11 : int
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…