Search code examples
haskellrecursionorder-of-executionrecursion-schemes

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