Top-down recursion schemes

Question

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.

Answer 1

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