自上而下的递归方案

Question

我们能否定义一个递归方案（不失去任何通用性）自上而下构造值，而不是自下而上-向上？

这将非常有帮助，因为我已经看到很多次在内部使用递归方案定义的函数首先将 reverse 应用于其输入，清楚地表明需要 foldl-like "front to back"执行。

Answer 1

虽然人们普遍认为 cata 有效 "bottom-up"，但它实际上可以表达许多 "top-down" 构造，通过使用参数为传递信息的函数实例化载体 "top-down":

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

这就是使用 foldr（对于列表是 cata）实现 foldl 或 reverse 的方法。

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

这是另一个按深度标记树的示例，从根开始计数：

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

自上而下的递归方案

Top-down recursion schemes

recursion

haskell

order-of-execution

recursion-schemes