自上而下的递归方案

Question

我们可以定义一个递归方案(不丢失任何通用性(来构造自上而下而不是自下而上的值吗？

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

Answer 1

尽管人们普遍认为cata"自下而上"地工作，但它实际上可以表达许多"自上而下"的结构，方法是使用一个函数实例化载体，该函数的参数是"自上而下"传递的信息：

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