什么是paramorphisms？

Question

通过阅读这篇经典论文,我坚持认为是paramorphisms.不幸的是,该部分非常薄,维基百科页面没有说什么.

我的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,什么是行动中的一些有用的例子？

---

是的,我已经看过这些 问题了,但是它们并没有直接涵盖paramorphisms,只指向可能有用作为参考的资源,而不是学习资料.

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"分支忽略其递归计算的参数并且只返回尾部.懒惰地评估,递归计算永远不会发生并且尾部在恒定时间内被提取.

你可以很容易地定义foldr使用para; 定义para起来有点棘手foldr,但它肯定是可能的,每个人都应该知道它是如何完成的!

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)

诀窍来定义para与foldr是重建一个副本的原始数据,使我们获得了在每一步进入到尾部的副本,即使我们不得不原来用不上.最后,snd丢弃输入的副本并仅提供输出值.这不是很有效率,但如果你对纯粹的表现力感兴趣,para那就给你带来的不仅仅是foldr.如果你使用这个foldr-encoded版本para,那么safeTail毕竟需要线性时间,按元素复制tail元素.

所以,就是这样:它para是一个更方便的版本,foldr它允许您立即访问列表的尾部以及从中计算的值.

在一般情况下,使用作为仿函数的递归修复点生成的数据类型

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

你有

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)

又一次,这两个是相互定义,与para从定义cata由相同的"制作副本"绝招

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

同样,如果您需要轻松访问输入的子结构,para则不再具有表现力cata,但更方便.

编辑:我记得另一个很好的例子.

考虑由Fix TreeFwhere 给出的二叉搜索树

data TreeF sub = Leaf | Node sub Integer sub

并尝试定义二进制搜索树的插入,首先作为a cata,然后作为a para.您会发现para版本更容易,因为在每个节点上您需要插入一个子树但保留另一个子节点.