# Top-down recursion schemes

Can we define a recursion scheme (without losing any of their generality) that constructs the value top-down, instead of bottom-up?

This would be quite helpful as I've seen plenty of times where the function, defined internally with a recursion scheme was first applying `reverse` to its input, clearly signalling the need for a `foldl`-like "front to back" execution.

Solution

• Although it's a common belief that `cata` works "bottom-up", it can actually express many "top-down" constructions, by instantiating the carrier with a function whose parameter is the information being passed "top-down":

``````cata :: (F  c       ->  c      ) -> Fix F -> c       -- general signature
:: (F (i -> d) -> (i -> d)) -> Fix F -> i -> d  -- with  c = (i -> d)
``````

That's how you can implement `foldl` or `reverse` using `foldr` (which is `cata` for lists).

``````--   foldl :: (b -> a -> b) -> b -> [a] -> b
-- using
--   foldr :: (a -> (b -> b) -> (b -> b)) -> (b -> b) -> [a] -> b -> b

foldl f b xs = foldr (\x go z -> go (f z x)) id xs b
``````

Here's another example to label a tree by depth, counting from the root:

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

makeBaseFunctor ''Tree  -- recursion-schemes

byDepth :: Tree a -> Tree Integer
byDepth t = cata byDepthF t 0 where
byDepthF :: TreeF a (Integer -> Tree Integer) -> Integer -> Tree Integer
byDepthF (NodeF u _ v) !d = Node (u (d + 1)) d (v (d + 1))
byDepthF LeafF = Leaf
``````