谁先说了下面的话?

monad只是内函子的范畴问题

另一个不太重要的问题是,这是真的吗?如果是的话,你能给出一个解释吗?


当前回答

这个特别的短语出自詹姆斯·伊里(James Iry)的《编程语言的简要、不完整和大部分错误的历史》(Brief,Incomplete and Mainly Error History of Programming Languages),他虚构地将其归因于菲利普·沃德勒(Philip Wadler)。

原文引用自《工作数学家的范畴》中的桑德斯-麦克莱恩,这是范畴理论的基础文本之一。这里是上下文,这可能是了解它确切含义的最佳场所。

但是,我要试试。原文如下:

总之,X中的单单体只是X的内函子范畴中的一个幺半群,乘积×被内函子的组合所取代,单位集被恒等式内函子所取代。

这里的X是一个类别。内函子是从一个范畴到它本身的函子(就函数程序员而言,通常是所有的函子,因为它们只处理一个范畴;类型的范畴——但我跑题了)。但你可以想象另一个范畴,即“X上的内函子”的范畴。这是一个范畴,其中对象是内函子,态射是自然变换。

在这些内函子中,有些可能是单核的。哪些是单子?正是那些在特定意义上是单胞体的。我将把它们各自的定义放在一起,让您进行比较,而不是拼写出从单子到幺半群的精确映射(因为MacLane做得比我希望的要好得多):

幺半群是。。。

A套,S操作,•:S×S→ SS,e:1的元素→ S

……符合这些法律:

(a•b)•c=a•(b•c),对于S中的所有a、b和ce•a=a•e=a,对于S中的所有a

莫纳德是。。。

内函子,T:X→ X(在Haskell中,一个类型为*->*的类型构造函数,带有一个Functor实例)自然变换,μ:T×T→ T、 其中,×表示函子组合(μ在Haskell中称为join)自然变换η:I→ T、 其中I是X上的恒等内函子(η在Haskell中称为返回)

……符合这些法律:

μTμ=μTμ∘Tη=μ\8728 ;ηT=1(恒等自然变换)

稍微眯一下眼睛,你可能会发现这两个定义都是同一个抽象概念的实例。

其他回答

这个特别的短语出自詹姆斯·伊里(James Iry)的《编程语言的简要、不完整和大部分错误的历史》(Brief,Incomplete and Mainly Error History of Programming Languages),他虚构地将其归因于菲利普·沃德勒(Philip Wadler)。

原文引用自《工作数学家的范畴》中的桑德斯-麦克莱恩,这是范畴理论的基础文本之一。这里是上下文,这可能是了解它确切含义的最佳场所。

但是,我要试试。原文如下:

总之,X中的单单体只是X的内函子范畴中的一个幺半群,乘积×被内函子的组合所取代,单位集被恒等式内函子所取代。

这里的X是一个类别。内函子是从一个范畴到它本身的函子(就函数程序员而言,通常是所有的函子,因为它们只处理一个范畴;类型的范畴——但我跑题了)。但你可以想象另一个范畴,即“X上的内函子”的范畴。这是一个范畴,其中对象是内函子,态射是自然变换。

在这些内函子中,有些可能是单核的。哪些是单子?正是那些在特定意义上是单胞体的。我将把它们各自的定义放在一起,让您进行比较,而不是拼写出从单子到幺半群的精确映射(因为MacLane做得比我希望的要好得多):

幺半群是。。。

A套,S操作,•:S×S→ SS,e:1的元素→ S

……符合这些法律:

(a•b)•c=a•(b•c),对于S中的所有a、b和ce•a=a•e=a,对于S中的所有a

莫纳德是。。。

内函子,T:X→ X(在Haskell中,一个类型为*->*的类型构造函数,带有一个Functor实例)自然变换,μ:T×T→ T、 其中,×表示函子组合(μ在Haskell中称为join)自然变换η:I→ T、 其中I是X上的恒等内函子(η在Haskell中称为返回)

……符合这些法律:

μTμ=μTμ∘Tη=μ\8728 ;ηT=1(恒等自然变换)

稍微眯一下眼睛,你可能会发现这两个定义都是同一个抽象概念的实例。

首先,我们将使用的扩展和库:

{-# LANGUAGE RankNTypes, TypeOperators #-}

import Control.Monad (join)

其中,RankNType是唯一一个对以下内容绝对重要的类型。我曾经写过一篇关于RankNTypes的解释,有些人似乎觉得它很有用,所以我会参考一下。

引用汤姆·克罗克特的出色回答,我们得出:

莫纳德是。。。一个内函子,T:X->X一个自然变换,μ:T×T->T,其中×表示函子组合一个自然变换,η:I->T,其中I是X上的恒等内函子……符合这些法律:μ(μ(T×T)×T))=μ(Tμ(η(T))=T=μ(T(η))

我们如何将其转换为Haskell代码?好吧,让我们从自然转变的概念开始:

-- | A natural transformations between two 'Functor' instances.  Law:
--
-- > fmap f . eta g == eta g . fmap f
--
-- Neat fact: the type system actually guarantees this law.
--
newtype f :-> g =
    Natural { eta :: forall x. f x -> g x }

形式为f:->g的类型类似于函数类型,但与其将其视为两种类型(类型*)之间的函数,不如将其视为由两个函子(类型*->*)组成的态射。示例:

listToMaybe :: [] :-> Maybe
listToMaybe = Natural go
    where go [] = Nothing
          go (x:_) = Just x

maybeToList :: Maybe :-> []
maybeToList = Natural go
    where go Nothing = []
          go (Just x) = [x]

reverse' :: [] :-> []
reverse' = Natural reverse

基本上,在Haskell中,自然转换是从某种类型f x到另一种类型g x的函数,这样x类型变量对调用者来说是“不可访问的”。例如,sort::Ord a=>[a]->[a]不能进行自然转换,因为它“挑剔”我们可以为a实例化哪些类型

函子是一种在不接触结构的情况下对某物内容进行操作的方式。自然转换是一种在不接触或不看内容的情况下对某物的结构进行操作的方式。

现在,让我们讨论一下定义的条款。

第一个子句是“一个内函子,T:X->X。”好吧,Haskell中的每个函子都是一个人们称之为“Hask范畴”的内函子。这听起来像一个复杂的陈述,但实际上是一个非常琐碎的陈述。这意味着,一个函子f::*->*为你提供了构造任何a::*的类型f::*以及从任何f::a->b中构造函数fmap f::fa->fb的方法,并且这些都遵循函子定律。

第二个子句:Haskell中的Identity函子(它随平台一起提供,因此您可以直接导入它)是这样定义的:

newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    fmap f (Identity a) = Identity (f a)

因此,Tom Crockett定义中的自然变换η:I->T可以这样写,适用于任何Monad实例T:

return' :: Monad t => Identity :-> t
return' = Natural (return . runIdentity)

第三条:Haskell中两个函子的组合可以这样定义(这也是平台附带的):

newtype Compose f g a = Compose { getCompose :: f (g a) }

-- | The composition of two 'Functor's is also a 'Functor'.
instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose fga) = Compose (fmap (fmap f) fga)

因此,来自汤姆·克罗克特定义的自然变换μ:T×T->T可以这样写:

join' :: Monad t => Compose t t :-> t
join' = Natural (join . getCompose)

这是内函子范畴中的幺半群的陈述意味着Compose(部分应用于它的前两个参数)是关联的,Identity是它的身份元素。即,以下同构成立:

合成f(合成g h)~=合成(合成f g)h组成f恒等式~=f合成恒等式g~=g

这些很容易证明,因为Compose和Identity都定义为newtype,而Haskell报告将newtype的语义定义为所定义的类型与newtype的数据构造函数的参数类型之间的同构。例如,让我们证明Compose f Identity ~=f:

Compose f Identity a
    ~= f (Identity a)                 -- newtype Compose f g a = Compose (f (g a))
    ~= f a                            -- newtype Identity a = Identity a
Q.E.D.

注意:不,这不是真的。在某个时刻,丹·皮波尼本人对这个答案发表了评论,他说这里的原因和结果完全相反,他写了一篇文章来回应詹姆斯·伊里的俏皮话。但它似乎已经被移除了,也许是因为某种强迫性的整理。

以下是我的原始答案。


Iry很可能读过《从幺半群到幺半群》(From Monoids to Monads),这篇文章中Dan Piponi(sigfpe)从Haskell中的幺半群导出了幺半群,并对范畴理论进行了大量讨论,明确提到了“Hask上的内函子范畴”。在任何情况下,任何想知道单单体是内函子范畴中的幺半群意味着什么的人都可以从阅读这个推导中受益。

我来到这篇文章是为了更好地理解MacLane的《工作数学家的范畴理论》中那句臭名昭著的名言的推论。

在描述什么是什么时,描述什么不是通常同样有用。

事实上,MacLane使用这个描述来描述Monad,这可能意味着它描述了Monad特有的东西。请听我说。为了对这一说法有更广泛的理解,我认为需要明确的是,他并不是在描述单子特有的东西;该声明同样描述了Applied和Arrows等。出于同样的原因,我们可以在Int上有两个幺半群(和和积),我们可以在内函子的范畴中在X上有几个幺半群。但这些相似之处甚至更多。

Monad和Applicative均符合以下标准:

endo=>在同一位置开始和结束的任何箭头或态射函子=>两个类别之间的任意箭头或态射(例如,在日常树a->列表b中,但在类别树->列表中)幺半群=>单个对象;即,单个类型,但在此上下文中,仅关于外部层;因此,我们不能有树->列表,只有列表->列表。

该语句使用“类别…”来定义语句的范围。例如,函子类别描述了f*->g*的范围,即任意函子->任意函子,例如Tree*->List*或Tree*->Tree*。

分类语句未指定的内容描述了允许的任何内容。

在这种情况下,在函子内部,*->*akaa->b没有被指定,这意味着Anything->Anything,包括Anything other。当我的想象跳到Int->String时,它还包括Integer->Maybe Int,甚至Maybe Double->Anywhere a::Maybe Double;b::字符串Int。

因此,声明如下:

函子作用域::f a->g b(即,任何参数化类型到任何参数化的类型)endo+函子::f a->f b(即,同一参数化类型的任何一个参数化类型)。。。换句话说,内函子范畴中的幺半群

那么,这种构造的力量在哪里?为了欣赏完整的动态,我需要看到一个幺半群的典型图形(看起来像一个身份箭头的单个对象,::single object->single object)未能说明我可以使用一个箭头,该箭头参数化了任意数量的幺半群值,来自monoid中允许的一个类型对象。等价的endo,~identity箭头定义忽略了函子的类型值以及最内部的“有效载荷”层的类型和值。因此,在函数类型匹配的任何情况下,等价性都会返回真(例如,Nothing->Just*->Nothing等价于Just*->Just*->Just*,因为它们都是Maybe->Maybe->Maybe)。

提要栏:~outside是概念性的,但它是f a中最左边的符号。它还描述了“Haskell”首先读到的内容(大图);因此Type相对于Type Value是“外部”的。编程中的层之间的关系(一系列引用)在Category中不易关联。集合的类别用于描述类型(Int、Strings、Maybe Int等),其中包括函数的类别(参数化类型)。引用链:Functor Type、Functor value(该Functor集合的元素,例如Nothing、Just),以及每个Functor值指向的其他所有元素。在Category中,对关系的描述不同,例如,return::a->m a被认为是从一个Functor到另一个Funtor的自然转换,与迄今为止提到的任何内容都不同。

回到主线,总的来说,对于任何定义的张量积和中性值,该语句最终描述了一个从其矛盾结构中诞生的惊人强大的计算构造:

在外部,它显示为单个对象(例如::List);静止的但在内部,允许很多动态同一类型的任意数量的值(例如,Empty | ~NonEmpty)作为任意arity函数的素材。张量积将把任意数量的输入减少到单个值。。。对于外层(~ fold,不涉及有效载荷)最内层的类型和值的无限范围

在Haskell中,澄清声明的适用性很重要。这个构造的强大和多功能性与monad本身完全无关。换句话说,这个构造不依赖于monad的独特之处。

当试图确定是否使用共享上下文来构建代码,以支持相互依赖的计算,而不是可以并行运行的计算时,这个臭名昭著的语句,尽管它描述了很多,但并不是Applied、Arrows和Monads的选择之间的对比,而是对它们的相同程度的描述。就目前的决定而言,这一声明毫无意义。

这经常被误解。该语句接着将join::m(m a)->m a描述为幺半群内函子的张量积。然而,它并没有明确说明,在本声明的上下文中,(<*>)也可以被选择。这确实是一个“六合一,六合一”的例子。组合值的逻辑完全相同;相同的输入从每个输入生成相同的输出(不同于Int的和和积幺半群,因为它们在组合Int时生成不同的结果)。

因此,概括一下:内函子范畴中的幺半群描述了:

 ~t :: m * -> m * -> m *
 and a neutral value for m *
    

(<*>)和(>>=)都提供对两个m值的同时访问,以便计算单个返回值。用于计算返回值的逻辑完全相同。如果不是它们参数化的函数的不同形状(f::a->b vs k::a->m b)以及具有相同计算返回类型的参数的位置(即,a->b->b vs b->a->b),我怀疑我们可以将单调逻辑(张量积)参数化,以便在两个定义中重复使用。作为一个练习,尝试并实现~t,最终会得到(<*>)和(>>=),这取决于您决定如何为所有b定义它。

如果我的最后一点至少在概念上是正确的,那么它解释了Applied和Monad之间的精确且唯一的计算差异:它们参数化的函数。换言之,差异在这些类型类的实现之外。

总之,根据我自己的经验,MacLane那句臭名昭著的名言提供了一个很棒的“goto”迷因,这是我在浏览类别时可以参考的指南,以更好地理解Haskell中使用的习语。它成功地捕捉到了强大的计算能力的范围,使其在Haskell中非常容易访问。

然而,讽刺的是,我第一次误解了该声明在monad之外的适用性,以及我希望在这里传达的内容。它所描述的一切都与Applied和Monads(以及Arrows等)相似。它没有说的恰恰是它们之间微小但有用的区别。

这里的答案在定义幺半群和幺半群方面做得很好,然而,它们似乎仍然不能回答这个问题:

另一个不太重要的问题是,这是真的吗?如果是的话,你能给出一个解释吗?

这里缺少的问题的关键是“幺半群”的不同概念,更准确地说是所谓的范畴化——幺半群在幺半群范畴中的概念。不幸的是,麦克·莱恩的书本身就让人很困惑:

总之,X中的单单体只是X的内函子范畴中的一个幺半群,乘积×被内函子的组合所取代,单位集被恒等式内函子所取代。

主要混淆

为什么这令人困惑?因为它没有定义什么是X的“内函子范畴中的幺半群”。相反,这句话建议将所有内函子集合中的一个幺半群与函子组合作为二元运算,将恒等函子作为幺半群单元。它工作得很好,并将包含恒等函子且在函子组合下闭合的任何内函子子集转化为幺半群。

然而,这并不是正确的解释,这本书在那个阶段并没有阐明。Monad f是一个固定的内函子,而不是在复合下闭合的内函子子集。一个常见的构造是使用f生成幺半群,方法是将f的所有k倍组成的集合f^k=f(f(…))与其自身进行比较,包括k=0,它对应于恒等式f^0=id。现在,所有k>=0的所有这些幂的集合S确实是一个幺半群“用乘积×替换为内函子的组成,单位集由恒等式内函子”。

然而:

这个幺半群S可以定义为任何函子f,甚至可以定义为X的任何自映射。由函子组合和恒等函子给出的S的幺半群结构与f是否为单单体无关。

更令人困惑的是,“幺半群范畴中的幺半群”的定义在书的后面,正如你从目录中看到的那样。然而,理解这一概念对于理解与单子叶的联系至关重要。

(严格)幺半类

转到关于幺半群的第七章(晚于关于单体的第六章),我们发现所谓的严格幺半群范畴的定义为三重(B,*,e),其中B是一个范畴,*:B x B->B是双函子(关于每个分量的函子,其他分量固定),e是B中的单位对象,满足结合性和单位定律:

(a * b) * c = a * (b * c)
a * e = e * a = a

对于b的任何对象a、b、c,以及e被id_e替换的任何态射a、b和c的同一恒等式,e的同一态射。现在可以观察到,在我们感兴趣的情况下,其中b是X的内函子的范畴,自然变换为态射,*函子组合,e是同一函子,所有这些定律都满足,这可以直接验证。

书中给出的是“放松的”单调范畴的定义,其中法则只对满足所谓相干关系的某些固定自然变换进行模运算,然而这对于我们的内函子范畴来说并不重要。

幺半群中的幺半群

最后,在第七章第3节“幺半群”中,给出了实际定义:

幺半群范畴(B,*,e)中的幺半群c是B的带有两个箭头的对象(态射)

mu: c * c -> c
nu: e -> c

使3个图可交换。回想一下,在我们的例子中,这些是内函子范畴中的态射,它们是自然变换,对应于单元的精确连接和返回。当我们将组合*变得更加明确时,这种联系变得更加清晰,用c^2替换c*c,其中c是我们的monad。

最后,请注意,3个交换图(在幺半类中幺半群的定义中)是为一般(非严格)幺半类而写的,而在我们的例子中,作为幺半类的一部分产生的所有自然变换实际上都是恒等式。这将使图表与monad定义中的图表完全相同,从而使对应关系完整。

结论

总之,根据定义,任何单元都是内函子,因此是内函子范畴中的对象,其中单元连接和返回运算符满足特定(严格)单元范畴中的幺半群的定义。反之亦然,根据定义,内函子的幺半群范畴中的任何幺半群都是由一个对象和两个箭头组成的三元组(c,mu,nu),例如在我们的例子中的自然变换,满足与单元相同的定律。

最后,注意(经典)幺半群和幺半群范畴中更一般的幺半群之间的关键区别。上面的两个箭头mu和nu不再是二进制运算和集合中的单位。相反,你有一个固定的内函子c。函子组合*和单位函子本身并不能提供单单体所需的完整结构,尽管书中有一句令人困惑的话。

另一种方法是与集合a的所有自映射的标准幺半群C进行比较,其中二元运算是合成,可以看出将标准笛卡尔积C x C映射到C。传递到分类幺半群,我们用函子合成*替换笛卡尔积x,二元运算用自然变换mu替换c*c到c,这是联接运算符的集合

join: c(c(T))->c(T)

对于每个对象T(编程中的类型)。而经典幺半群中的单位元,可以用来自固定一点集的映射图像来识别,被返回算子的集合所取代

return: T->c(T) 

但是现在没有更多的笛卡尔乘积,所以没有成对的元素,因此没有二进制运算。