Histomorphisms，Zygomorphisms和Futumorphisms专门用于列表 [英] Histomorphisms, Zygomorphisms and Futumorphisms specialised to lists
问题描述
为了理解泛型递归方案（即使用 Fix ），我发现编写各种方案的列表版本是很有用的。它使理解实际方案变得更容易（没有 Fix 东西）的额外开销）。
，我还没有想出如何定义 zygo 和 futu 的仅限列表版本。
以下是我迄今为止的专门定义：
cataL ::（a - > b→b）→> b - > [a] - > b
cataL fb（a：as）= fa（cataL fb as）
cataL _ b [] = b
paraL ::（a - > [a] - > b - > b） - > b - > [a] - > b
paraL fb（a：as）= fa as（paraL fb as）
paraL _ b [] = b
- TODO：histo
- DONE：zygo（见下文）
anaL ::（b - >（a，b）） - > b - > [a]
anaL fb = let（a，b'）= fb in a：anaL f b'
anaL'::（b - > Maybe（a，b）） - > b - > [a]
anaL'f b =
的情况f b只要（a，b'） - > a：anaL'f b'
Nothing - > []
apoL ::（[b] - >可能（a，或者[b] [a]）） - > [b] - > [a]
apoL f b =
的情况f b无 - > []
Just（x，Left c） - > x：apoL f c
Just（x，Right e） - > x：e
- DONE：futu（见下文）
hyloL ::（a - > c - > c） - > c - > （b→> Maybe（a，b））→> b - > c
hyloL f z g = cataL f z。 aaL'g
hyloL'::（a - > c - > c） - > c - > （c - > Maybe（a，c）） - > c
hyloL'f z g = case g z of
Nothing - > z
Just（x，z'） - >你如何定义 histo
$ b $> / code>， zygo 和 futu 列表吗？解决方案 Zygomorphism 是我们赋予由两个半互相递归函数构建的折叠的高福祉的数学名称。我将举一个例子。
设想一个函数 pm :: [Int] - > + 和 - 的（for plus- minus 交替地通过数字列表，使得 pm [v，w，x，y，z] = v-（w +（x-（y + z）））。您可以使用原始递归将其写出：
lengthEven :: [a] - > Bool
lengthEven =偶数。长度
pm0 [] = 0
pm0（x：xs）=如果lengthEven xs
则x - pm0 xs
else x + pm0 xs
显然 pm0 不是构图 - 您需要检查每个位置整个列表的长度，以确定您是添加还是减去。 Paramorphism
模拟了这种类型的原始递归，当折叠函数需要在折叠的每次迭代中遍历整个子树时。因此，我们至少可以重写代码以符合已建立的模式。
paraL ::（a - > [a] - > b - > b） - > b - > [a] - > b
paraL fz [] = z
paraL fz（x：xs）= fx xs（paraL fz xs）
pm1 = paraL（\ x xs acc - >如果lengthEven xs那么x - acc else x + acc）0
但这是低效的。 lengthEven 在每次迭代中遍历整个列表，导致O（n <2>）算法。
我们可以通过指出 lengthEven 和 para 可以用 foldr ...
<$ p表示为 catamorphism $ p> cataL = foldr
lengthEven'= cataL（\_ p - > not p）True
paraL'fz = snd。 cataL（\ x（xs，acc） - >（x：xs，fx xs acc））（[]，z）
......这表明我们可能能够将这两个操作融合到一个列表中。 code> pm2 = snd。 cataL（\ x（isEven，total） - >（not isEven，if isEven
then x - total
else x + total））（True，0）
我们有一个取决于另一个折叠结果的折叠，我们可以将它们融合到列表的一个遍历中。
zygoL ::（a - > b - > b） - > - 折叠函数
（a - > b - > c - > c） - > - 取决于另一个折叠结果的折叠功能
b - > c - > - 两次折数
[a] - > c
zygoL f g z e = snd。 cataL（\ x（p，q） - >（fxp，gxpq））（z，e）
在每次迭代中， f 从最后一次迭代看到它在变形中的答案，但是 g 可以看到两个函数的答案。 g 与 f 纠结。
通过使用第一个折叠函数来计算列表的长度是偶数还是奇数，第二个用来计算总数，将 pm 写为一个自洽型。
pm3 = zygoL（\_ p - > not p）（\ x isEven total - > if isEven
then x - 总
else x + total）True 0
这是经典的函数式编程风格。我们有一个更高级的功能来完成消耗清单的繁重工作;我们所要做的只是插入逻辑来汇总结果。结构明显终止（您只需证明终止 foldr ），并且它比原始手写版本更有效。
Aside ：@AlexR在评论中指出，zygomorphism有一个名叫mutumorphism的大姐妹，它捕捉到互相递归所有的
荣耀。 mutu generalises zygo 在两者折叠的
函数允许检查b
$ b
mutuL ::（a - > b - > c - > b） - >
（a - > b - > c - > c） - >
b - > c - >
[a] - > c
mutuL f g z e = snd。 cataL（\ x（p，q） - >（fxpq，gxpq））（z，e）
只要忽略额外的参数，就可以从 mutu 中恢复 zygo 。
zygoL f = mutuL（\ xpq - > fxp）
当然，所有这些折叠模式都从列表概括为任意函子的固定点：
newtype Fix f = Fix {unFix :: f（Fix f）}
cata :: Functor f => （f a - > a） - >修复f - >
cata f = f。 fmap（cata f）。 unFix
para :: Functor f => （f（Fix f，a） - > a） - >修复f - > a
para f = snd。 cata（\ x - >（Fix $ fmap fst x，f x））
zygo :: Functor f => （f b - > b） - > （f（b，a） - > a） - >修复f - >
zygo f g = snd。 cata（\ x - >（f $ fmap fst x，g x））
mutu :: Functor f => （f（b，a） - > b） - > （f（b，a） - > a） - >修复f - >
mutu f g = snd。 cata（\ x - >（fx，gx））
比较 zygo 和 zygoL 。还要注意 zygo Fix = para ，后三个折叠可以用 cata 来实现。在折衷论中，一切都与其他一切有关。
您可以从广义版本中恢复列表版本。
数据ListF ar = Nil_ | Cons_a r导出Functor
类型List a = Fix（ListF a）
zygoL'::（a - > b - > b） - > （a→b→c→c）→> b - > c - >列表a - > c
zygoL'fgze = zygo kl
其中k Nil_ = z
k（Cons_ xy）= fxy
l Nil_ = e
l（Cons_ x（y，z）） = gxyz
pm4 = zygoL'（\_ p - > not p）（\ x isEven total - > if isEven
then x - total
else x + total）True 0
In my effort to understand generic recursion schemes (i.e., that use Fix) I have found it useful to write list-only versions of the various schemes. It makes it much easier to understand the actual schemes (without the additional overhead of the Fix stuff).
However, I have not yet figured out how to define list-only versions of zygo and futu.
Here are my specialised definitions so far:
cataL :: (a -> b -> b) -> b -> [a] -> b
cataL f b (a : as) = f a (cataL f b as)
cataL _ b [] = b
paraL :: (a -> [a] -> b -> b) -> b -> [a] -> b
paraL f b (a : as) = f a as (paraL f b as)
paraL _ b [] = b
-- TODO: histo
-- DONE: zygo (see below)
anaL :: (b -> (a, b)) -> b -> [a]
anaL f b = let (a, b') = f b in a : anaL f b'
anaL' :: (b -> Maybe (a, b)) -> b -> [a]
anaL' f b = case f b of
Just (a, b') -> a : anaL' f b'
Nothing -> []
apoL :: ([b] -> Maybe (a, Either [b] [a])) -> [b] -> [a]
apoL f b = case f b of
Nothing -> []
Just (x, Left c) -> x : apoL f c
Just (x, Right e) -> x : e
-- DONE: futu (see below)
hyloL :: (a -> c -> c) -> c -> (b -> Maybe (a, b)) -> b -> c
hyloL f z g = cataL f z . anaL' g
hyloL' :: (a -> c -> c) -> c -> (c -> Maybe (a, c)) -> c
hyloL' f z g = case g z of
Nothing -> z
Just (x,z') -> f x (hyloL' f z' g)
How do you define histo, zygo and futu for lists?
解决方案 Zygomorphism is the high-falutin' mathsy name we give to folds built from two semi-mutually recursive functions. I'll give an example.
Imagine a function pm :: [Int] -> Int (for plus-minus) which intersperses + and - alternately through a list of numbers, such that pm [v,w,x,y,z] = v - (w + (x - (y + z))). You can write it out using primitive recursion:
lengthEven :: [a] -> Bool
lengthEven = even . length
pm0 [] = 0
pm0 (x:xs) = if lengthEven xs
then x - pm0 xs
else x + pm0 xs
Clearly pm0 is not compositional - you need to inspect the length of the whole list at each position to determine whether you're adding or subtracting. Paramorphism models primitive recursion of this sort, when the folding function needs to traverse the whole subtree at each iteration of the fold. So we can at least rewrite the code to conform to an established pattern.
paraL :: (a -> [a] -> b -> b) -> b -> [a] -> b
paraL f z [] = z
paraL f z (x:xs) = f x xs (paraL f z xs)
pm1 = paraL (\x xs acc -> if lengthEven xs then x - acc else x + acc) 0
But this is inefficient. lengthEven traverses the whole list at each iteration of the paramorphism resulting in an O(n2) algorithm.
We can make progress by noting that both lengthEven and para can be expressed as a catamorphism with foldr...
cataL = foldr
lengthEven' = cataL (\_ p -> not p) True
paraL' f z = snd . cataL (\x (xs, acc) -> (x:xs, f x xs acc)) ([], z)
... which suggests that we may be able to fuse the two operations into a single pass over the list.
pm2 = snd . cataL (\x (isEven, total) -> (not isEven, if isEven
then x - total
else x + total)) (True, 0)
We had a fold which depended on the result of another fold, and we were able to fuse them into one traversal of the list. Zygomorphism captures exactly this pattern.
zygoL :: (a -> b -> b) -> -- a folding function
(a -> b -> c -> c) -> -- a folding function which depends on the result of the other fold
b -> c -> -- zeroes for the two folds
[a] -> c
zygoL f g z e = snd . cataL (\x (p, q) -> (f x p, g x p q)) (z, e)
On each iteration of the fold, f sees its answer from the last iteration as in a catamorphism, but g gets to see both functions' answers. g entangles itself with f.
We'll write pm as a zygomorphism by using the first folding function to count whether the list is even or odd in length and the second one to calculate the total.
pm3 = zygoL (\_ p -> not p) (\x isEven total -> if isEven
then x - total
else x + total) True 0
This is classic functional programming style. We have a higher order function doing the heavy lifting of consuming the list; all we had to do was plug in the logic to aggregate results. The construction evidently terminates (you need only prove termination for foldr), and it's more efficient than the original hand-written version to boot.
Aside: @AlexR points out in the comments that zygomorphism has a big sister called mutumorphism, which captures mutual recursion in all
its glory. mutu generalises zygo in that both the folding
functions are allowed to inspect the other's result from the previous
iteration.
mutuL :: (a -> b -> c -> b) ->
(a -> b -> c -> c) ->
b -> c ->
[a] -> c
mutuL f g z e = snd . cataL (\x (p, q) -> (f x p q, g x p q)) (z, e)
You recover zygo from mutu simply by ignoring the extra argument.
zygoL f = mutuL (\x p q -> f x p)
Of course, all of these folding patterns generalise from lists to the fixpoint of an arbitrary functor:
newtype Fix f = Fix { unFix :: f (Fix f) }
cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unFix
para :: Functor f => (f (Fix f, a) -> a) -> Fix f -> a
para f = snd . cata (\x -> (Fix $ fmap fst x, f x))
zygo :: Functor f => (f b -> b) -> (f (b, a) -> a) -> Fix f -> a
zygo f g = snd . cata (\x -> (f $ fmap fst x, g x))
mutu :: Functor f => (f (b, a) -> b) -> (f (b, a) -> a) -> Fix f -> a
mutu f g = snd . cata (\x -> (f x, g x))
Compare the definition of zygo with that of zygoL. Also note that zygo Fix = para, and that the latter three folds can be implemented in terms of cata. In foldology everything is related to everything else.
You can recover the list version from the generalised version.
data ListF a r = Nil_ | Cons_ a r deriving Functor
type List a = Fix (ListF a)
zygoL' :: (a -> b -> b) -> (a -> b -> c -> c) -> b -> c -> List a -> c
zygoL' f g z e = zygo k l
where k Nil_ = z
k (Cons_ x y) = f x y
l Nil_ = e
l (Cons_ x (y, z)) = g x y z
pm4 = zygoL' (\_ p -> not p) (\x isEven total -> if isEven
then x - total
else x + total) True 0
这篇关于Histomorphisms，Zygomorphisms和Futumorphisms专门用于列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
