Sorry my last comment was sort of wrong because I neglected to mention Fix (I'm going to claim that I was tired :) ).
They say a picture is worth a thousand words, so hopefully this clears up the difference betwene `out` and `toTreeF`:
-- | Our basic binary tree type
data Tree a = Leaf a | Node (Tree a) (Tree a)
-- | A pattern functor for our binary tree
data TreeF a r = LeafF a | NodeF r r
-- | The fixed point of 'f'.
newtype Fix f = Fix { unfix :: f (Fix f) }
-- | Given an F-Algebra on 'f' we have a catamorphism on 'Fix f'
cata :: Functor f => Algebra f a -> Fix f -> a
cata alg fix = alg $ fmap (cata alg) $ unfix fix
-- | We can sum the elements of a 'Fix (TreeF Int)' using 'cata'
sumTreeF :: Fix (TreeF Int) -> Int
sumTreeF = cata $ \case
LeafF i x -> x + i
NodeF l r x -> x + l + r
-- | To operate our binary tree we need to map from 'Tree a' to 'TreeF
-- a'.
toTreeF :: Tree a -> Fix (TreeF a)
toTreeF = \case
Leaf a -> LeafF a
Node l r -> NodeF (toTreeF l) (toTreeF r)
sumTree :: Tree Int -> Int
sumTree = sumTreeF . toTreeF
I didn't compile this code but it should be correct.
out :: Fix (TreeF a) -> TreeF a (Fix (TreeF a))
toTreeF -> Tree a -> Fix (TreeF a)
Yeah you could do that but now you have thrown away the recursive `Tree` type and are always working in `TreeF`. This is totally fine but is a different design decision from where we started.
They say a picture is worth a thousand words, so hopefully this clears up the difference betwene `out` and `toTreeF`:
I didn't compile this code but it should be correct.