Monads作为附属物

编辑：只是为了好玩，我会做对的。原始答案保留在下面 类别附加的当前附加代码现在位于附件包中：http：//hackage.haskell.org/package/adjunctions 我只是明确而简单地通过状态monad工作。此代码使用变压器包中的

Data.Functor.Compose

，但在其他方面是独立的。 f（D - > C）和g（C - > D）之间的附加，写成f - | g，可以以多种方式表征。我们将使用counit / unit（epsilon / eta）描述，它给出了两个自然变换（仿函数之间的态射）。

class (Functor f, Functor g) => Adjoint f g where
     counit :: f (g a) -> a
     unit   :: a -> g (f a)

请注意，coun中的“a”实际上是C中的身份函子，而单元中的“a”实际上是D中的身份函子。 我们还可以从counit / unit定义中恢复hom-set adjunction定义。

phiLeft :: Adjoint f g => (f a -> b) -> (a -> g b)
phiLeft f = fmap f . unit

phiRight :: Adjoint f g => (a -> g b) -> (f a -> b)
phiRight f = counit . fmap f

在任何情况下，我们现在可以从我们的单位/国家协议中定义一个Monad，如下所示：

instance Adjoint f g => Monad (Compose g f) where
    return x = Compose $ unit x
    x >>= f  = Compose . fmap counit . getCompose $ fmap (getCompose . f) x

现在我们可以实现（a，）和（a - >）之间的经典附加：

instance Adjoint ((,) a) ((->) a) where
    -- counit :: (a,a -> b) -> b
    counit (x, f) = f x
    -- unit :: b -> (a -> (a,b))
    unit x = y -> (y, x)

现在是一个类型的同义词

type State s = Compose ((->) s) ((,) s)

如果我们在ghci中加载它，我们可以确认State正是我们的经典状态monad。请注意，我们可以使用相反的组合并获取Costate Comonad（也就是商店comonad）。 我们可以用这种方式制作一些其他的附加功能（例如（Bool，）），但它们有点奇怪的单子。不幸的是，我们不能以令人愉快的方式直接在Haskell中执行引导Reader和Writer的附加功能。我们可以做Cont，但正如copumpkin所描述的那样，它需要来自相反类别的附加，所以它实际上使用了“伴随”类型类的不同“形式”来反转某些箭头。该形式也在附属包中的不同模块中实现。 Derek Elkins在Monad Reader 13中的文章以不同的方式介绍了这一材料 - 用类别理论计算单子：http：//www.haskell.org/wikiupload/8/85/TMR-Issue13.pdf 此外，Hinze最近的Kan扩展程序优化论文还介绍了从

Mon

和

Set

之间的附件中构建monad列表：http：//www.cs.ox.ac.uk/ralf.hinze/Kan.pdf 老答案： 两个参考。 1）类别附加物一如既往地传递附加物的表示以及它们如何产生单子。像往常一样，很好地思考，但很好的文档：http：//hackage.haskell.org/packages/archive/category-extras/0.53.5/doc/html/Control-Functor-Adjunction.html 2）-Cafe还提供了关于附加作用的有希望但简短的讨论。其中一些可能有助于解释类别附加：http：//www.haskell.org/pipermail/haskell-cafe/2007-December/036328.html     

Derek Elkins最近在晚餐时向我展示了Cont Monad是如何通过将

(_ -> k)

逆变函子与其自身组合而产生的，因为它恰好是自我伴随的。这就是你如何得到它的

(a -> k) -> k

。然而，它的反对导致双重否定消除，这不能用Haskell写出来。 对于一些说明并证明这一点的Agda代码，请参阅http://hpaste.org/68257。     

这是一个老线程，但我发现这个问题很有趣， 所以我自己做了一些计算。希望Bartosz还在那里 并且可能会读到这个.. 实际上，在这种情况下，Eilenberg-Moore的结构确实给出了非常清晰的图景。 （我将使用CWM表示法与Haskell一样的语法） 设

T

为monad

< T,eta,mu >

（

eta = return

和

mu = concat

） 并考虑T代数

h:T a -> a

。 （注意

T a = [a]

是一个自由的幺ѭѭѭ，即身份

[]

和乘法

(++)

。） 根据定义，

h

必须满足

h.T h == h.mu a

和

h.eta a== id

。 现在，一些简单的图表追逐证明

h

实际上诱导了一个幺半群结构（由

x*y = h[x,y]

定义）， 并且

h

成为这种结构的幺半群同态。 相反，Haskell中定义的任何幺半群结构

< a,a0,* >

自然地定义为T-代数。 通过这种方式（

h = foldr ( * ) a0

，'用'28'替换'

(:)

，并将

[]

映射到

a0

，该身份的功能）。 因此，在这种情况下，T-代数的类别只是在Haskell，HaskMon中可定义的幺半群结构的类别。 （请检查T-algebras中的态射实际上是单态同态。） 它还将列表描述为HaskMon中的通用对象，就像Grp中的免费产品，CRng中的多项式环等。 对应于上述结构的调整是

< F,G,eta,epsilon >

哪里

F:Hask -> HaskMon

，它取一个类型为'由'33'生成的'自由幺半群'，即

[a]

，

G:HaskMon -> Hask

，健忘的算子（忘记乘法），

eta:1 -> GF

，由

x::a -> [x]

定义的自然变换，

epsilon: FG -> 1

，由上述折叠函数定义的自然变换                 （从一个自由的幺半群到它的商幺'的'规范投射'） 接下来，还有另一个'Kleisli类别'和相应的附加功能。 你可以检查它只是具有态射H39ѭ的Haskell类型， 它的成分由所谓的“Kleisli成分”

(>=>)

给出。 典型的Haskell程序员会发现这个类别更为熟悉。 最后，如CWM中所示，T-代数的类别 （相应的Kleisli类别）成为类别中的终端（resp.initial）对象 在合适的意义上定义列表单子T的辅助剂。 我建议对二叉树仿函数

T a = L a | B (T a) (T a)

进行类似的计算以检查你的理解。     

我已经为Eilenberg-Moore找到了任何monad的辅助仿函数的标准结构，但我不确定它是否会增加任何洞察力。构造中的第二类是T-代数。 T代数在初始类别中添加“产品”。 那么它如何适用于列表monad呢？列表monad中的仿函数由类型构造函数（例如，

Int->[Int]

）和函数映射（例如，映射到列表的标准应用）组成。代数添加从列表到元素的映射。一个例子是添加（或乘以）整数列表的所有元素。仿函数

F

采用任何类型，例如Int，并将其映射到Int列表中定义的代数，其中产品由monadic join定义（反之亦然，join定义为产品）。健忘的算子

G

取代数并忘记了产品。然后使用伴随仿函数对

F

，

G

以通常的方式构造monad。 我必须说我不是更聪明的人。     

如果你有兴趣，这里有一些非专家的想法 关于monad和adjunction在编程语言中的作用： 首先，对于给定的monad

T

，存在对Kle10ѭ的Kleisli类别的唯一附加。 在Haskell中，monad的使用主要局限于此类别的操作  （基本上是一类免费代数，没有商）。 事实上，所有人都可以用Haskell Monad来组成一些Kleisli态射 键入

a->T b

通过使用do表达式，

(>>=)

等来创建新的 射。在这种情况下，monad的作用仅限于经济 表示法。一个利用态射的相关性能够写（比如说）

[0,1,2]

而不是

(Cons 0 (Cons 1 (Cons 2 Nil)))

，也就是说，你可以把序列写成序列， 不是一棵树。 即使使用IO monads也不是必需的，因为当前的Haskell类型系统功能强大 足以实现数据封装（存在类型）。 这是我对原始问题的回答， 但我很好奇Haskell专家对此有何看法。 另一方面，正如我们已经注意到的那样，monad和。之间也存在1-1的对应关系 （T-）代数的附加。按照麦克莱恩的说法，选择是一种方式 表达类别的等价性。 在adj53ѭ的典型设置中，

F

是某种类型 '自由代数发生器'和G''健忘的仿函数'，相应的monad 将（通过使用T-代数）描述

A

的代数结构是如何（和何时）构造在

X

的对象上的。 在Hask和列表monad T的情况下，

T

引入的结构是 of monoid，这可以帮助我们通过代数建立代码的属性（包括正确性） 幺半群理论提供的方法。例如，函数

foldr (*) e::[a]->a

可以 只要

<a,(*),e>

是一个幺半群，很容易被视为联想操作， 可以由编译器利用的事实来优化计算（例如，通过并行）。 另一个应用是使用分类来识别和分类函数式编程中的“递归模式” 希望（部分）处理'函数式编程的转向'，Y（任意递归组合器）的方法。 显然，这种应用程序是类别理论创建者（MacLane，Eilenberg等）的主要动机之一， 即，建立类别的自然等价，并将一种众所周知的方法转移到一个类别中 到另一个（例如拓扑空间的同源方法，编程的代数方法等）。 在这里，adjoints和monad是利用这种类别连接不可或缺的工具。 （顺便提一下，monad（及其双重，comonads）的概念是如此普遍，以至于人们甚至可以定义'cohomologies' Haskell类型。但我还没有想过。） 至于你提到的非决定性功能，我更不用说了...... 但请注意;如果某个类别

A

的附加

<F,G>:Hask->A

定义了monad

T

列表， 必须有一个独特的“比较函子”

K:A->MonHask

（Haskell中可定义的幺半群类别），见CWM。 实际上，这意味着您的兴趣类别必须是某种限制形式的幺半群类别（例如，它可能缺少一些商而不是免费代数）以便定义列表monad。 最后，一些评论： 我在上一篇文章中提到的二叉树仿函数很容易推广到任意数据类型

T a1 .. an = T1 T11 .. T1m | ...

。 也就是说，Haskell中的任何数据类型都自然地定义了monad（连同相应的代数类别和Kleisli类别）， 这只是Haskell中任何数据构造函数的结果。 这是我认为Haskell的Monad类不仅仅是语法糖的另一个原因 （当然，这在实践中非常重要）。