什么是参数形态学？

Question

阅读这篇经典论文时，我卡在了参数形式上。不幸的是，这一部分非常薄，而维基百科页面也没有提到任何内容。

我的Haskell翻译如下：

para :: (a -> [a] -> b -> b) -> b -> [a] -> b
para f base = h
  where
    h []       =   base
    h (x:xs)   =   f x xs (h xs)

但我不理解那个——我对类型签名或所需结果没有任何直觉。

什么是paramorphism，有哪些有用的示例？

---

是的，我看过这些 问题, 但它们没有直接涉及参数形式，只指向资源可能作为参考资料有所帮助，但不适合作为学习材料。

- Matt Fenwick

---

我认为这段代码是这样的：para f base xs = foldr (uncurry f) base $ zip xs (tail $tails xs)。 - Daniel Fischer

根据这个维基页面的解释，参数形式（paramorphisms）可以“对归纳数据类型进行原始递归建模”。这是否有任何意义或帮助呢？ - huon

我在其中一篇评论中提到的Jeremy Gibbons的"Fission"论文是非常有用的学习资料。http://www.cs.ox.ac.uk/jeremy.gibbons/publications/fission.pdf 它清晰地介绍了许多递归模式。 - stephen tetley

Daniel的重写可以简化为para f base xs = foldr g base (init $ tails xs) where g (x:xs) = f x xs。这让我想起了Common Lisp的maplist。 - Will Ness

Answer 1

是的，那就是 para。与catamorphism或foldr相比：

para  :: (a -> [a] -> b -> b) -> b -> [a] -> b
foldr :: (a ->        b -> b) -> b -> [a] -> b

para  c n (x : xs) = c x xs (para c n xs)
foldr c n (x : xs) = c x    (foldr c n xs)
para  c n []       = n
foldr c n []       = n

有些人将 paramorphisms 称为“原始递归”，与 catamorphisms（foldr）的“迭代”相对应。

在这里，foldr 的两个参数为输入数据的每个递归子对象计算一个递归值（即列表的尾部），而 para 的参数既包括原始子对象，也包括从它递归计算得出的值。

一个很好地表达了使用 para 的示例函数是收集列表的合适后缀。

suff :: [x] -> [[x]]
suff = para (\ x xs suffxs -> xs : suffxs) []

为了使得

suff "suffix" = ["uffix", "ffix", "fix", "ix", "x", ""]

可能更简单的方法是：

safeTail :: [x] -> Maybe [x]
safeTail = para (\ _ xs _ -> Just xs) Nothing

在“cons”分支中，忽略了其递归计算的参数，并只返回其尾部。如果按惰性求值方式进行计算，则递归计算将永远不会发生，且可在常数时间内提取其尾部。

可以使用“para”很容易地定义“foldr”；从“foldr”定义“para”则需要稍微花点儿心思，但是它肯定是可行的，每个人都应该知道如何完成！

foldr c n =       para  (\ x  xs  t ->           c x    t)       n
para  c n = snd . foldr (\ x (xs, t) -> (x : xs, c x xs t)) ([], n)

使用foldr定义para的技巧是重构原始数据的副本，这样我们就可以在每一步中访问尾部的副本，即使我们没有访问原始数据。最后，snd丢弃输入的副本并只给出输出值。这不是很高效，但如果您对纯表现力感兴趣，para与foldr相比并没有更多的优势。如果您使用这个foldr编码版本的para，那么safeTail最终将花费线性时间，逐个复制尾元素。

所以，para是foldr的更方便版本，它让您立即访问列表的尾部以及从中计算出的值。

在一般情况下，使用作为函子的递归不动点生成的数据类型。

data Fix f = In (f (Fix f))

you have

cata :: Functor f => (f         t  -> t) -> Fix f -> t
para :: Functor f => (f (Fix f, t) -> t) -> Fix f -> t

cata phi (In ff) = phi (fmap (cata phi) ff)
para psi (In ff) = psi (fmap keepCopy   ff) where
  keepCopy x = (x, para psi x)

再次强调，两者是相互定义的，使用相同的“复制”技巧从cata中定义para

para psi = snd . cata (\ fxt -> (In (fmap fst fxt), psi fxt))

再次强调，para并没有比cata更具表现力，但如果需要轻松访问输入的子结构，则更为方便。

编辑：我想起了另一个好例子。

考虑由Fix TreeF给出的二叉搜索树，其中

data TreeF sub = Leaf | Node sub Integer sub

尝试定义二叉搜索树的插入，首先作为 cata ，然后作为 para 。您会发现 para 版本更容易，因为在每个节点上，您需要在一个子树中插入，但保留另一个子树不变。

- pigworker