haskell - 自顶向下递归方案

Question

我们能否定义一个递归方案（不失其一般性）来构造值 top-down而不是自下而上？

这将非常有帮助，因为我已经看到很多次使用递归方案在内部定义的函数首先应用于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)

---

这就是您可以实现foldl或reverse使用的foldr方式（cata用于列表）。

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