haskell - 自上而下的递归方案

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