haskell - 什么是异态？

Question

通读this classic paper ，我陷入了拟态。不幸的是，该部分非常薄，维基百科页面没有说明任何内容。

我的 Haskell 翻译是:

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

但我不明白这一点——我对类型签名或所需的结果没有任何直觉。

什么是拟态，有哪些有用的例子？

<小时/>

是的，我见过these questions ，但它们不直接涵盖同态，仅指向 resources作为引用可能会有帮助，但不能作为学习 Material 。

Answer 1

是的，那就是para。与变形或 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

有些人将同态称为“原始递归”，而变态 (foldr) 则称为“迭代”。

其中 foldr 的两个参数为输入数据的每个递归子对象(这里是列表的尾部)提供了一个递归计算值，para' s 参数获取原始子对象和从中递归计算的值。

用 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。如果您使用 para 的 foldr 编码版本，那么 safeTail 毕竟会花费线性时间，逐个元素复制尾部。

所以，就是这样: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)

再说一次，两者是可以相互定义的，通过相同的“复制”技巧从 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 版本更容易，因为在每个节点上，您需要插入一个子树，但保留另一个子树原样。