haskell 专门用于列表的组织形态、接合形态和未来形态

dw1jzc5e  于 2022-11-14  发布在  其他
关注(0)|答案(3)|浏览(189)

最后我终于明白了。请看我演讲的视频和幻灯片：

原始问题：
在我努力理解通用递归模式（即使用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？

haskell

3条答案

按热度按时间
w1e3prcc

w1e3prcc1#

Zygomorphism是我们给由两个半相互递归函数构成的折叠所取的一个夸张的数学名称。
想象一个函数pm :: [Int] -> Int（表示 plus-minus），它交替地将+和-穿插在一串数字中，使得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不是compositional--你需要检查整个列表在每个位置的长度，以确定你是在加还是在减。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在paramorphism的每次迭代中遍历整个列表，导致O（n2）算法。
我们可以通过注意到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)

我们有一个折叠依赖于另一个折叠的结果，我们能够将它们融合到列表的一次遍历中，接合形态正好捕捉到了这种模式。

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)

只需忽略额外的参数，即可从mutu恢复zygo。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
赞(0）分享  回复(0）举报  2022-11-14
dfuffjeb

dfuffjeb2#

  • 组织形态学 * 模型 * 动态编程 *，将先前子计算的结果制成表格的技术。在组织形态中，折叠函数可以访问折叠的早期迭代的结果表。将此与退化进行比较，其中折叠函数只能看到最后一次迭代的结果。组织形态学有后见之明的好处-你可以看到所有的历史。

思路是这样的：当我们使用输入列表时，折叠代数会输出一个b s序列。histo会记下出现的每个b，并将其附加到结果表中。历史中的项数等于您处理的列表层数--当您拆下整个列表时，操作历史记录的长度将与列表的长度相等。
下面是列表（ory）的迭代历史：

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

History是一个由事件和结果组成的列表，在末尾有一个额外的结果，对应于[]-事件。

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

(It碰巧History a是一个comonad，但是headH（née extract）是我们定义histoL所需要的全部。）
History用其相应的结果标记输入列表的每一层。cofree comonad 捕获标记任意结构的每一层的模式。

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

（我通过将ListF插入Cofree并进行简化，得出了History。）
把它与自由单子相比较，

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

Free是联产品类型; Cofree是产品类型。Free将f的千层面分层，在千层面的底部具有值a。Cofree将千层面分层，在每一层具有值a。自由单子是广义的外部标记树;共生自由共生单胞菌是广义的内部标记树。
有了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。组织形态见过去;未来形态可以预测未来。就像cata f . ana g可以融合成一个 hylomorphism 一样，histo f . futu g也可以融合成一个chronomorphism。
即使你跳过了数学部分，this paper by Hinze and Wu也提供了一个很好的、示例驱动的关于组织形态及其用法的教程。

赞(0）分享  回复(0）举报  2022-11-14
hgc7kmma

hgc7kmma3#

由于还没有其他人回答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总是返回，您将永远不会陷入等待下一个列表元素的困境）。

赞(0）分享  回复(0）举报  2022-11-14
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com