haskell - Haskell 中 Cofree CoMonad 的一些激励示例是什么？

Question

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

比如我想玩Cofree [] Num在 ghci 中，并不能得到任何有趣的例子。

例如，如果我构造一个 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]

Answer 1

让我们回顾一下 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

对于列表，我们被标记为玫瑰树。

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

这些结构总是“非空”的，因为至少有一个顶级节点，即使它没有子节点，而且那个节点总是有一个标签。 extract操作为您提供顶级节点的标签。

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

即， extract丢弃顶部标签的上下文。

现在， 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操作是身份 co-Kleisli 箭头，由 extend 解释作为恒等函数。当然还有Kleisli的合奏

(=<=) :: 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 范畴到集合和函数的仿函数(在分类意义上)。这些法律不难查 Cofree ，因为它们来自 Functor节点形状的规律。

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

a :< fca

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

Cofree ((->) move) prize

此服务器的客户端必须停止，或通过提供 move 继续: 这是 move 的列表s。比赛进行如下:

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)相当于一个只有“发送 move”命令的命令界面。仿函数 ((->) move)是对应的结构“响应 move 的发送”。

一些仿函数可以看作是捕获命令接口(interface)；这种仿函数的自由 monad 代表发出命令的程序；仿函数将有一个“双重”，表示如何响应命令； dual 的 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)