什么是paramorphisms？ [英] What are paramorphisms?
问题描述
通读这篇经典论文，我被困在paramorphisms。不幸的是，该部分非常薄，维基百科页面没有任何说明。
我的Haskell翻译是：
para ::（a - > [a] - > b - > b） - > b - > [a] - > b
para f base = h
其中
h [] = base
h（x：xs）= fx xs（h xs）
但是我不赞成 - 我没有任何类型签名或期望结果的直觉。
什么是paramorphism，什么是一些有用的例子？
是的，我已经看过这些 问题，但它们不直接覆盖paramorphisms，只指向 resources ，可能有助于引用，但不能作为学习资料。 >解决方案
是的，这是 para 。与catamorphism比较，或 foldr ：
para ::（a - > [a] - > b - > b） - > b - > [a] - > b
foldr ::（a - > b - > b） - > b - > [a] - > b
para cn（x：xs）= cx xs（para cn xs）
foldr cn（x：xs）= cx（foldr cn xs）
para cn [] = n
foldr cn [] = n
有些人称paramorphisms为primitive recursion与变形（ foldr ）的对比是迭代。
其中 foldr 的两个参数给出了递归计算的值，用于输入数据的每个递归子对象（这里是列表的尾部）， para 的参数获得原始子对象和递归计算的值。
用 para 很好地表达的示例函数是
suff :: [x] - > [[x]]
suff = para（\ x xs suffxs - > xs：suffxs）[]
以便
suffsuffix= [uffix，ffix，fix， ix，x，]
可能更简单仍然是
safeTail :: [x] - >也许[x]
safeTail = para（\ _ xs _ - > Just xs）Nothing
其中cons分支忽略了它的递归计算的参数并且仅仅给出尾部。懒惰地评估，递归计算永远不会发生，并且尾部会在一段时间内被提取出来。
您可以定义 foldr para 很容易;从 foldr 定义 para 是有点棘手的，但这当然是可能的，每个人都应该知道它是如何完成的！ / p>
foldr cn = para（\ x xs t - > cxt）n
para cn = snd。 foldr（\ x（xs，t） - >（x：xs，cx xs t））（[]，n）
使用 foldr 定义 para 的技巧是重建一个 copy 原始数据，这样我们就可以在每个步骤访问尾部副本，即使我们无法访问原始数据。最后， snd 放弃输入的副本，并只给出输出值。这不是很有效，但如果你对透明度感兴趣， para 不会超过 foldr 。如果您使用 foldr - para 的编码版本，那么 safeTail para 是一个更方便的 foldr 版本，它使您能够立即访问列表的尾部以及从中计算出的值。
在一般情况下，使用作为函数的递归固定点生成的数据类型
data数据修复f = In（f（Fix f））
您有
cata :: Functor f => （f t - > t） - >修复f - > t
para :: Functor f => （f（Fix f，t）→t）→>修复f - > t
cata phi（ff）= phi（fmap（cata phi）ff）
para psi（In ff）= psi（fmap keepCopy ff）其中
keepCopy x = （x，para psi x）
这两者是可以相互定义的，<$ c $通过相同的复制技巧从 cata 定义的c> para
para psi = snd。 cata（\ fxt - >（In（fmap fst fxt），psi fxt））
， para 不会比 cata 更具表现力，但如果您需要轻松访问输入的子结构，则更方便。 / b>
编辑：我记得另一个很好的例子。
修复TreeF 其中 数据TreeF sub = Leaf | Node sub Integer sub
尝试为二叉搜索树定义插入，首先是 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.
这篇关于什么是paramorphisms？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
