What is the correct definition of `unfold` for an unlabelled tree?

Question

I was thinking about how to implement the unfold equivalent for the following type:

 data Tree a = Node (Tree a) (Tree a) | Leaf a | Nil 

This did not immediately become apparent, since the standard unfold for lists returns the value and the next seed. For this data type, this does not make sense, since there is no value until you reach the node sheet. So it really makes sense to return new seeds or stop with value. I use this definition:

 data Drive sa = Stop | Unit a | Branch ss deriving Show unfold :: (t -> Drive ta) -> t -> Tree a unfold fn x = case fn x of Branch ab -> Node (unfold fn a) (unfold fn b) Unit a -> Leaf a Stop -> Nil main = print $ unfold go 5 where go 0 = Stop go 1 = Unit 1 go n = Branch (n - 1) (n - 2) 

While this works, I’m not sure how it should be. So here is the question: what is the right way to do this?

Answer 1

If you think the data type is a fixed point on the functor, you can see that your definition is a reasonable generalization of the list.

 module Unfold where 

Here we begin by definition a fixed point of the functor f : this is the layer f , followed by another fixed point:

 newtype Fix f = InFix { outFix :: f (Fix f) } 

To make things clearer, here are the definitions of functors corresponding to lists and trees. They have basically the same form as data types, except that we have replaced the recursive calls with an additional parameter. In other words, they describe what a single list / tree layer looks like and are common to possible r substructures.

 data ListF ar = LNil | LCons ar data TreeF ar = TNil | TLeaf a | TBranch rr 

Lists and trees are respectively fixed points of ListF and TreeF:

 type List a = Fix (ListF a) type Tree a = Fix (TreeF a) 

In any case, having downloaded that you now have the best intuition about this fixed-point business, we can see that there is a general way to define unfold functions for them.

Given the original seed, as well as the function that takes the seed and creates one layer f , where the recursive structure is the new seeds, we can build the whole structure:

 unfoldFix :: Functor f => (s -> fs) -> s -> Fix f unfoldFix node = go where go = InFix . fmap go . node 

This definition specializes in the usual unfold list or your definition for trees. In other words: your definition was indeed correct.