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.
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