Histomorphisms,Zygomorphisms和Futumorphisms专门列出

Question

我最终搞清楚了.请参阅我给出的演讲的视频和幻灯片:

• 幻灯片/ PDF

• 视频

原始问题:

在我努力理解通用递归方案(即使用Fix)时,我发现编写各种方案的仅列表版本很有用.它使得理解实际方案变得更加容易(没有额外的开销Fix).

但是,我还没有想出如何定义只列出版本zygo和futu.

以下是我目前的专门定义:

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)

你是如何定义histo,zygo以及futu对列表？

Answer 1

Zygomorphism是我们给由两个半互相递归函数构建的折叠的高falutin'数学名称.我举个例子.

想象一个函数pm :: [Int] -> Int(对于正 - 负),它穿插+并-交替通过一个数字列表,这样pm [v,w,x,y,z] = v - (w + (x - (y + z))).你可以使用原始递归来写出来:

lengthEven :: [a] -> Bool
lengthEven = even . length

pm0 [] = 0
pm0 (x:xs) = if lengthEven xs
             then x - pm0 xs
             else x + pm0 xs

显然pm0不是成分 - 您需要检查每个位置的整个列表的长度,以确定您是添加还是减去.当折叠函数需要在折叠的每次迭代中遍历整个子树时,Paramorphism模拟这种类型的原始递归.所以我们至少可以重写代码以符合已建立的模式.

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

但这效率低下.lengthEven在每次迭代的遍历中遍历整个列表,得到O(n ²)算法.

我们可以通过注意两者lengthEven并且para可以表达为与... 的交互性来取得进展foldr.

cataL = foldr

lengthEven' = cataL (\_ p -> not p) True
paraL' f z = snd . cataL (\x (xs, acc) -> (x:xs, f x xs acc)) ([], z)

...这表明我们可以将两个操作融合到列表中的单个传递中.

pm2 = snd . cataL (\x (isEven, total) -> (not isEven, if isEven
                                                      then x - total
                                                      else x + total)) (True, 0)

我们有一个折叠取决于另一个折叠的结果,我们能够将它们融合到列表的一个遍历中.Zygomorphism正好捕获了这种模式.

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)

在折叠的每次迭代中,f从最后一次迭代中看到它的回答,如同在一个变形中,但是g看到两个函数的答案.g与...纠缠在一起f.

pm通过使用第一个折叠函数来计算列表的长度是偶数还是奇数,第二个用于计算总数,我们将写为对称性.

pm3 = zygoL (\_ p -> not p) (\x isEven total -> if isEven
                                                then x - total
                                                else x + total) True 0

这是经典的函数式编程风格.我们有一个更高阶的功能来完成消耗列表的繁重工作; 我们所要做的就是插入逻辑来汇总结果.该结构显然终止(您只需要证明终止foldr),并且它比原始的手写版本更有效.

除此之外:@AlexR在评论中指出,对称有一个叫做mutumorphism的大姐,它捕获了所有荣耀中的相互递归.mutu可以推广zygo在两个折叠功能被允许从先前的迭代检查对方的结果.

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)

您恢复zygo从mutu简单地忽略额外的参数. zygoL f = mutuL (\x p q -> f x p)

当然,所有这些折叠模式都从列表推广到任意仿函数的固定点:

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))

比较定义zygo与zygoL.的定义.还要注意,zygo Fix = para后三个折叠可以用来实现cata.在折叠学中,一切都与其他一切有关.

您可以从通用版本恢复列表版本.

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

Answer 2

由于还没有其他人回答futu,我会试图绊倒我的方式.我打算用ListF a b = Base [a] = ConsF a b | NilF

采用的类型recursion-schemes:futu :: Unfoldable t => (a -> Base t (Free (Base t) a)) -> a -> t.

我将忽略Unfoldable约束并替换[b]为t.

(a -> Base [b] (Free (Base [b]) a)) -> a -> [b]
(a -> ListF b (Free (ListF b) a)) -> a -> [b]

Free (ListF b) a)是一个列表,可能a在末尾有一个圆形孔.这意味着它是同构的([b], Maybe a).所以现在我们有:

(a -> ListF b ([b], Maybe a)) -> a -> [b]

消除最后一个ListF,注意到ListF a b同构的Maybe (a, b):

(a -> Maybe (b, ([b], Maybe a))) -> a -> [b]

现在,我很确定玩类型俄罗斯方块会导致唯一明智的实现:

futuL f x = case f x of
  Nothing -> []
  Just (y, (ys, mz)) -> y : (ys ++ fz)
    where fz = case mz of
      Nothing -> []
      Just z -> futuL f z

总结得到的函数,futuL获取种子值和可能产生至少一个结果的函数,并且如果产生结果,则可能产生新的种子值.

起初我认为这相当于

notFutuL :: (a -> ([b], Maybe a)) -> a -> [b]
notFutuL f x = case f x of
  (ys, mx) -> ys ++ case mx of
    Nothing -> []
    Just x' -> notFutuL f x'

在实践中,也许它或多或少,但一个显着的区别是真正的futu保证生产力(即如果f总是返回,你永远不会被困在下一个列表元素永远等待).

Answer 3

组织模型模拟动态编程,即将先前子计算的结果制成表格的技术.(它有时被称为过程归纳法.)在组织形态中,折叠函数可以访问折叠的早期迭代结果的表.将其与catamorphism进行比较,其中折叠函数只能看到最后一次迭代的结果.组织形态具有后见之明的好处 - 你可以看到所有的历史.

这是个主意.当我们使用输入列表时,折叠代数将输出一系列bs.histo将在每个b出现时记下每一个,并将其附在结果表中.历史记录中的项目数等于您已处理的列表图层数 - 当您拆除整个列表时,操作历史记录的长度将等于列表的长度.

这就是迭代列表(ory)的历史:

data History a b = Ancient b | Age a b (History a b)

History是一对事物和结果的列表,在结尾处对应于[]-thing 的额外结果.我们将输入列表的每一层与其对应的结果配对.

cataL = foldr

history :: (a -> History a b -> b) -> b -> [a] -> History a b
history f z = cataL (\x h -> Age x (f x h) h) (Ancient z)

从右到左折叠整个列表后,最终结果将位于堆栈顶部.

headH :: History a b -> b
headH (Ancient x) = x
headH (Age _ x _) = x

histoL :: (a -> History a b -> b) -> b -> [a] -> b
histoL f z = headH . history f z

(碰巧这History a是一个comonad,但是headH(née extract)是我们需要定义的histoL.)

History标记输入列表的每一层及其相应的结果.所述cofree comonad捕获标记的任意结构的每一层的图案.

data Cofree f a = Cofree { headC :: a, tailC :: f (Cofree f a) }

(我想出了History通过插入ListF到Cofree和简化.)

与免费monad相比,

data Free f a = Free (f (Free f a))
              | Return a

Free是副产品类型; Cofree是一种产品类型.Free在千层面上加一层千层面f,价值a在烤宽面条的底部.Cofree将每层的价值叠加在千层面上a.免费monad是外化标记的树; cofree comonads是通用的内部标记树.

随着Cofree在手,我们可以从列表推广到任意函子的不动点,

newtype Fix f = Fix { unFix :: f (Fix f) }

cata :: Functor f => (f b -> b) -> Fix f -> b
cata f = f . fmap (cata f) . unFix

histo :: Functor f => (f (Cofree f b) -> b) -> Fix f -> b
histo f = headC . cata (\x -> Cofree (f x) x)

并再一次恢复列表版本.

data ListF a r = Nil_ | Cons_ a r deriving Functor
type List a = Fix (ListF a)
type History' a b = Cofree (ListF a) b

histoL' :: (a -> History' a b -> b) -> b -> List a -> b
histoL' f z = histo g
    where g Nil_ = z
          g (Cons_ x h) = f x h

旁白:histo是双重的futu.看看他们的类型.

histo :: Functor f => (f (Cofree f a) -> a) -> (Fix f -> a)
futu  :: Functor f => (a  ->  f (Free f a)) -> (a -> Fix f)

futu是histo用箭头翻转并Free替换为 Cofree.组织学看到了过去; futumorphisms预测未来.很像cata f . ana g可以融合成一个hylomorphism, histo f . futu g可以融合成一个 chronomorphism.

即使你跳过数学部分,Hinze和Wu的这篇论文也提供了一个关于组织形态及其用法的好的,以实例为导向的教程.