haskell - Haskell中的Cofree CoMonad有哪些激励性的例子？

我一直在玩Cofree，不能完全理解它。

例如，我想在ghci中使用Cofree [] Num，并且无法获得任何有趣的示例。

例如，如果我构造一个Cofree类型:

let a = 1 :< [2, 3]

我期望extract a == 1，但我收到此错误:

No instance for (Num (Cofree [] a0)) arising from a use of ‘it’
    In the first argument of ‘print’, namely ‘it’
    In a stmt of an interactive GHCi command: print it

和一种:

extract a :: (Num a, Num (Cofree [] a)) => a

我可以举一些简单的示例，甚至是琐碎的示例，说明如何将Cofree与函子一起使用:[]或Maybe或Either，该示例演示了

extract

extend

unwrap

duplicate吗？

交叉发布:https://www.reddit.com/r/haskell/comments/4wlw70/what_are_some_motivating_examples_for_cofree/

编辑:在David Young的评论指导下，以下是一些更好的示例，这些示例显示了我的第一次尝试被误导的地方，但是我仍然喜欢一些可以指导Cofree直觉的示例:

> let a = 1 :< []
> extract a
    1
> let b = 1 :< [(2 :< []), (3 :< [])]
> extract b
    1
> unwrap b
    [2 :< [],3 :< []]
> map extract $ unwrap b
    [2,3]

最佳答案

让我们回顾一下Cofree数据类型的定义。

data Cofree f a = a :< f (Cofree f a)

至少足以诊断出示例中的问题。当你写

1 :< [2, 3]

您犯了一个小错误，报告的结果微妙得多，无济于事。在这里，f = []和a是数字值，因为1 :: a。相应地，您需要

[2, 3] :: [Cofree [] a]

因此

2 :: Cofree [] a

如果Cofree [] a也是Num的实例，则可以。因此，您的定义获得了一个不可能满足的约束，实际上，当您使用自己的值时，满足该约束的尝试将失败。

再试一次

1 :< [2 :< [], 3 :< []]

而且你应该有更好的运气。

现在，让我们看看我们所拥有的。首先保持简单。什么是Cofree f ()？ Cofree [] ()特别是什么？后者与[]的固定点同构:树结构，其中每个节点是子树的列表，也称为“未标记的玫瑰树”。例如。，

() :< [  () :< [  () :< []
               ,  () :< []
               ]
      ,  () :< []
      ]

同样，Cofree Maybe ()或多或少是Maybe的固定点:自然数的副本，因为Maybe给我们提供了零位或一个位置来插入子树。

zero :: Cofree Maybe ()
zero = () :< Nothing
succ :: Cofree Maybe () -> Cofree Maybe ()
succ n = () :< Just n

一个重要的小例子是Cofree (Const y) ()，它是y的副本。 Const y函子不提供子树的位置。

pack :: y -> Cofree (Const y) ()
pack y = () :< Const y

接下来，让我们忙于另一个参数。它告诉您附加到每个节点的标签类型。更有意义地重命名参数

data Cofree nodeOf label = label :< nodeOf (Cofree nodeOf label)

当我们标记(Const y)示例时，我们得到了对

pair :: x -> y -> Cofree (Const y) x
pair x y = x :< Const y

当我们在数字的节点上附加标签时，我们会得到非空列表

one :: x -> Cofree Maybe x
one = x :< Nothing
cons :: x -> Cofree Maybe x -> Cofree Maybe x
cons x xs = x :< Just xs

对于 list ，我们得到了标有玫瑰树的标签。

0 :< [  1 :< [  3 :< []
             ,  4 :< []
             ]
     ,  2 :< []
     ]

这些结构始终是“非空”的，因为即使没有子节点，也至少有一个顶部节点，并且该节点将始终具有标签。 extract操作为您提供顶部节点的标签。

extract :: Cofree f a -> a
extract (a :< _) = a

也就是说，extract丢弃了top标签​​的上下文。

现在，duplicate操作使用其自身的上下文装饰每个标签。

duplicate :: Cofree f a -> Cofree f (Cofree f a)
duplicate a :< fca = (a :< fca) :< fmap duplicate fca  -- f's fmap

我们可以通过访问整个树来获取Functor的Cofree f实例

fmap :: (a -> b) -> Cofree f a -> Cofree f b
fmap g (a :< fca) = g a :< fmap (fmap g) fca
    --                     ^^^^  ^^^^
    --                 f's fmap  ||||
    --                           (Cofree f)'s fmap, used recursively

不难看出

fmap extract . duplicate = id

因为duplicate用上下文来装饰每个节点，所以fmap extract放弃了装饰。

请注意，fmap仅查看输入的标签以计算输出的标签。假设我们要根据上下文中的每个输入标签来计算输出标签？例如，给定一个未标记的树，我们可能想用整个子树的大小标记每个节点。多亏了Foldable的Cofree f实例，我们应该能够对节点进行计数。

length :: Foldable f => Cofree f a -> Int

所以这意味着

fmap length . duplicate :: Cofree f a -> Cofree f Int

comonads的关键思想是它们捕获“具有某些上下文的事物”，并且它们使您可以将依赖于上下文的映射应用于所有位置。

extend :: Comonad c => (c a -> b) -> c a -> c b
extend f = fmap f       -- context-dependent map everywhere
           .            -- after
           duplicate    -- decorating everything with its context

更直接地定义extend可以避免重复的麻烦(尽管这仅意味着共享)。

extend :: (Cofree f a -> b) -> Cofree f a -> Cofree f b
extend g ca@(_ :< fca) = g ca :< fmap (extend g) fca

您可以通过获取duplicate返回

duplicate = extend id -- the output label is the input label in its context

此外，如果您选择extract作为对每个上下文标签的处理方式，则只需将每个标签放回其来源:

extend extract = id

这些“在上下文标签上的操作”称为“co-Kleisli箭头”，

g :: c a -> b

extend的工作是将co-Kleisli箭头解释为整个结构上的函数。 extract操作是身份共Kleisli箭头，由extend解释为身份函数。当然，有一个共同的克莱斯里组合

(=<=) :: Comonad c => (c s -> t) -> (c r -> s) -> (c r -> t)
(g =<= h) = g . extend h

comonad法则确保=<=具有关联性并吸收extract，从而为我们提供了共同Kleisli类别。而且我们有

extend (g =<= h)  =  extend g . extend h

因此extend是从co-Kleisli类别到set-and-functions的函子(从类别意义上来说)。这些定律不难检查Cofree，因为它们遵循节点形状的Functor定律。

现在，在cofree社区中查看结构的一种有用方法是作为一种“游戏服务器”。结构

a :< fca

代表游戏状态。游戏中的移动包括“停止”(在这种情况下您获得a)或“继续”(通过选择fca的子树)。例如，考虑

Cofree ((->) move) prize

该服务器的客户端必须停止，或者通过提供move继续:这是move的列表。游戏进行如下:

play :: [move] -> Cofree ((->) move) prize -> prize
play []       (prize :< _) = prize
play (m : ms) (_     :< f) = play ms (f m)

也许move是Char，而prize是解析字符序列的结果。

如果您足够凝视，您会看到[move]是Free ((,) move) ()的版本。免费的monad代表客户策略。函子((,) move)相当于一个命令界面，仅命令“send a move”。函子((->) move)是相应的结构“响应move的发送”。

一些函子可以看作是捕获命令界面。此类函子的免费monad表示发出命令的程序；函子将具有一个“双重”，代表如何响应命令；对偶的cofree comonad是环境的一般概念，在该环境中可以运行发出命令的程序，其中标签表示如果程序停止并返回一个值该怎么办，而子结构表示如果该程序停止并返回值，则如何继续运行。它发出命令。

例如，

data Comms x = Send Char x | Receive (Char -> x)

描述允许发送或接收字符。它的双重是

data Responder x = Resp {ifSend :: Char -> x, ifReceive :: (Char, x)}

作为练习，看看是否可以实现交互

chatter :: Free Comms x -> Cofree Responder y -> (x, y)

关于haskell - Haskell中的Cofree CoMonad有哪些激励性的例子？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38816993/