什么是拟态? [英] What are paramorphisms?

问题描述

通读这篇经典论文，我被困在paramorphisms上.不幸的是，该部分很薄，维基百科页面没有说明任何内容.

我的 Haskell 翻译是:

para :: (a -> [a] -> b -> b) ->b->[a] ->乙对 f 基数 = h在哪里h [] = 基数h (x:xs) = f x xs (h xs)

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

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

<小时>

是的，我看过这些 问题，但它们不直接涵盖准同态，仅指向资源，可能作为参考有用，但不能作为学习材料.

解决方案

是的，那就是 para.与 catamorphism 或 foldr 进行比较:

para :: (a -> [a] -> b -> b) ->b->[a] ->乙foldr :: (a -> b -> b) ->b->[a] ->乙para c n (x : xs) = c x xs (para c n xs)foldr c n (x : xs) = c x (foldr c n xs)对 c n [] = n文件夹 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] ->也许 [x]safeTail = para ( _ xs _ -> Just xs) 什么都没有

其中cons"分支忽略其递归计算的参数，只返回尾部.惰性求值，递归计算永远不会发生，并且在恒定时间内提取尾部.

你可以很容易地使用para来定义foldr；从 foldr 定义 para 有点棘手，但这当然是可能的，每个人都应该知道它是如何完成的！

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

使用foldr 定义para 的技巧是重建原始数据的copy，以便我们可以访问每一步都有尾巴，即使我们无法访问原始文件.最后，snd 丢弃输入的副本，只给出输出值.这不是很有效，但是如果您对纯粹的表现力感兴趣，para 给您的只是foldr.如果你使用这个 foldr 编码的 para 版本，那么 safeTail 毕竟将花费线性时间，逐个元素复制尾部元素.>

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

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

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

你有

cata :: Functor f =>(f t -> t) ->修复 f ->吨para :: 函子 f =>(f (Fix f, t) -> t) ->修复 f ->吨cata phi (In ff) = phi (fmap (cata phi) ff)para psi (In ff) = psi (fmap keepCopy ff) 其中keepCopy x = (x, para psi x)

再说一次，两者是相互定义的，para从cata通过相同的制作副本"技巧定义

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

同样，para 并不比 cata 更具表现力，但如果您需要轻松访问输入的子结构，它会更方便.

我想起了另一个很好的例子.

考虑由 Fix TreeF where

给出的二叉搜索树

data TreeF sub = Leaf |节点子 整数子

并尝试定义二叉搜索树的插入，首先定义为 cata，然后定义为 para.您会发现 para 版本要容易得多，因为在每个节点上，您需要插入一个子树，但保留另一个子树的原样.

Reading through this classic paper, I'm stuck on paramorphisms. Unfortunately the section is quite thin, and the Wikipedia page doesn't say anything.

My Haskell translation is:

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

But I don't grok that -- I don't have any intuition for the type signature or the desired result.

What's a paramorphism, and what are some useful examples in action?

---

Yes, I've seen these questions, but they don't cover paramorphisms directly and only point to resources that may be helpful as references, but not as learning materials.

解决方案

Yes, that's para. Compare with catamorphism, or 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

Some people call paramorphisms "primitive recursion" by contrast with catamorphisms (foldr) being "iteration".

Where foldr's two parameters are given a recursively computed value for each recursive subobject of the input data (here, that's the tail of the list), para's parameters get both the original subobject and the value computed recursively from it.

An example function that's nicely expressed with para is the collection of the proper suffices of a list.

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

so that

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

Possibly simpler still is

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

in which the "cons" branch ignores its recursively computed argument and just gives back the tail. Evaluated lazily, the recursive computation never happens and the tail is extracted in constant time.

You can define foldr using para quite easily; it's a little trickier to define para from foldr, but it's certainly possible, and everyone should know how it's done!

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)

The trick to defining para with foldr is to reconstruct a copy of the original data, so that we gain access to a copy of the tail at each step, even though we had no access to the original. At the end, snd discards the copy of the input and gives just the output value. It's not very efficient, but if you're interested in sheer expressivity, para gives you no more than foldr. If you use this foldr-encoded version of para, then safeTail will take linear time after all, copying the tail element by element.

So, that's it: para is a more convenient version of foldr which gives you immediate access to the tail of the list as well as the value computed from it.

In the general case, working with a datatype generated as the recursive fixpoint of a functor

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)

and again, the two are mutually definable, with para defined from cata by the same "make a copy" trick

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

Again, para is no more expressive than cata, but more convenient if you need easy access to substructures of the input.

Edit: I remembered another nice example.

Consider binary search trees given by Fix TreeF where

data TreeF sub = Leaf | Node sub Integer sub

and try defining insertion for binary search trees, first as a cata, then as a para. You'll find the para version much easier, as at each node you will need to insert in one subtree but preserve the other as it was.

这篇关于什么是拟态?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！