Creating a Custom Fold Function for Custom Tree

Question

I'm attempting to create my own fold function which I can then use on my custom tree.

My Tree is simple like so:

data Stem a = Node (Stem a) (Stem a) | Leaf a

I want to be able to build a foldTree function which works much in the same way as foldr would.

I've manage to get it to work for when n=1 or just a leaf with the following

foldTree :: (x -> u -> u) -> u -> Stem x -> u
foldTree f a (Leaf o) = f o a

But I can't seem to work out the next line (IE for when there are nodes and leafs), I understand I need to recursively call foldTree but I'm not sure how I can do it. I've tried the following but I'm not having much luck.

foldTree f a (Node l r) = f a (foldTree f a l) (foldTree f a r)

This doesn't work as I know my parameters are x -> u -> u and so I've got one too many parameters. Although this is where I am stuck I'm not sure how to traverse both paths correctly.

So all together I have

foldTree :: (x -> u -> u) -> u -> Stem x -> u
foldTree f a (Leaf o) = f o a
foldTree f a (Node l r) = f a (foldTree f a l) (foldTree f a r) <-- Not working

How can I update this second line (or possibly something else in the method to get it to work?

Thanks for the help!

A fold will repeatably apply the given function to individual elements, with the previous result as one of the inputs. There will be an order to this, it essentially turns your structure into a flat sequence. Think about how you want to do this for your data structure. What order do you want to apply the function in? Essentially what I'm asking is how can you turn `Stem a` into `[a]`? At which point you don't need to write your own fold, you can use the built-in one for lists. — bheklilr, Mar 30 '17 at 13:59
I know I could make use of the inbuilt ones but the book I'm working through suggested I try one of these exercises, so I know it is possible but I'm having trouble figuring it out. (And unfortunately it doesn't come with the answers for this one ) — Liably, Mar 30 '17 at 14:02
`(x -> u -> u)` looks wrong to me, are you sure you don't want `(x -> x -> u)` instead? I would expect this: `foldTree :: (x -> x -> u) -> (x -> u) -> Stem x -> u` — chi, Mar 30 '17 at 14:09
I'm sorry chi, but I don't understand how you came to that conclusion, would d you mind possibly explaining how how / why you think that? — Liably, Mar 30 '17 at 14:12
This question is now closed as a duplicate, but the tree in the duplicate question uses a different tree type (with data in the internal nodes instead of in the leaves). This changes the type of the `fold` function a bit, but the essence of the solution is the same. — chi, Mar 30 '17 at 14:14
@chi oh, good point. I can re-open the question, but as you say it is nonetheless very similar in essence. What do you think? — Benjamin Hodgson, Mar 30 '17 at 14:15
Your question is definitely a duplicate as marked by @BenjaminHodgson, but in case you don't find the answer you're looking for in the linked question I had one mostly written up already that you can find [here](https://gist.github.com/anonymous/f0537497faeeb775392eee79fdd9a9f7) — bheklilr, Mar 30 '17 at 14:16
Thank you Bheklilr, @BenjaminHodgson I may not have a vote but surely this isn't an "exact duplicate" do to the difference in tree type as chi mentioned. — Liably, Mar 30 '17 at 14:18
There's a general rule for folds: each constructor becomes a fold argument. Roughly, if the constructor has type, say `K :: T a -> A -> B -> a -> T a` then the corresponding argument has type `(u -> A -> A -> a -> u)` -- each `T a` is replaced by `u`, and other types are left as they are, where `u` is the final return type of `fold`. — chi, Mar 30 '17 at 14:19
@chi You're talking about catamorphisms. I think the questioneer wanted a crush, ie a monoidal accumulation, ie a `Foldable.foldr`. — Benjamin Hodgson, Mar 30 '17 at 14:20
@BenjaminHodgson I'm unsure. We are probably so used to see catas that we put them in the "seen-one-seen-all" basket. For a beginner, however, relatively minor differences could be significant obstacles. — chi, Mar 30 '17 at 14:22
@BenjaminHodgson Ahh! I see! I was mislead by the OP when he said "like `foldr`". To the OP: there's a chance that I was speaking of the "other" fold (I _really_ wish that `Foldable` was named something else!), which might not what you want. So, feel free to ignore what I said :-/ — chi, Mar 30 '17 at 14:25
So @BenjaminHodgson, What am I to do, that question you marked as duplicate really does not help me. Yes someone who is experienced in Haskell may be able to see the differences but as Chi says I'm new to this so I'm really struggling here to understand what I need to do. It's even harder when you close the question and point me to one which isn't "an exact duplicate" — Liably, Mar 30 '17 at 14:36
@Liably Reopened. For posterity here is the question I originally thought was a dupe: http://stackoverflow.com/questions/39180630/fold-tree-function — Benjamin Hodgson, Mar 30 '17 at 14:57
Thank you, @bheklilr if you wish to paste your answer you provided in our chat I'll accept it. Thank you — Liably, Mar 30 '17 at 15:26

score 2 · Accepted Answer · answered Mar 30 '17 at 15:50

Work on the simple, specific cases first, and then extend the logic to the general cases. You have the easy one, for Leaf:

foldTree f a (Leaf o) = f o a

Then think about what you want to happen where there's a Node with only two Leafs:

foldTree f a (Node (Leaf x) (Leaf y)) = _

Here we know that f will have to be applied twice, but in what order? Let's just start with the Leaf in the first slot of Node:

foldTree f a (Node (Leaf x) (Leaf y)) = _ (f x a)

I've left the hole (_) in the expression because GHC will actually tell you what type of thing needs to go there when you try to compile. In this case, it'll say that you need something of type u -> u since f x a :: u. Well, we know that f :: x -> u -> u, so we can write

foldTree f a (Node (Leaf x) (Leaf y)) = f _ (f x a)

Now the only thing that can fill this hole is y from the right leaf, so

foldTree f a (Node (Leaf x) (Leaf y)) = f y (f x a)

But we know that f x a is the same as foldTree f a (Leaf x), so we can substitute that in:

foldTree f a (Node (Leaf x) (Leaf y)) = f y (foldTree f a (Leaf x))

Then replace Leaf x with just a single variable:

foldTree f a (Node left (Leaf y)) = f y (foldTree f a left)

If you squint your eyes and look closely, you'll see the same pattern a second time. Just do a quick substitution

foldTree f a (Node left (Leaf y)) = f y a'
  where a' = foldTree f a left

Now you can do the substitution

foldTree f a (Node left right) = foldTree f a' right
  where a' = foldTree f a left

And the whole definition is

foldTree f a (Leaf x) = f x a
foldTree f a (Node left right) = foldTree f (foldTree f a left) right

Double check your left-to-right orientation. The question requests `foldr`. This solution delivers neither `foldl` nor `foldr`. But the edit distance is small. — pigworker, Mar 30 '17 at 23:56

Creating a Custom Fold Function for Custom Tree

1 Answers1