最后,一个monoid必须是 associative . (只要你没有't change the left-to-right-order of objects) Addition is OK ((5+3)+1 == 5+(3+1)), but subtraction isn' t((5-3)-1!= 5-(3-1)),你可以随意减少一长串组合 .
-- | 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 的类型类似于函数类型,但不是将其视为两种类型(类型 * )之间的函数,而是将其视为两个 functors (各种类型 * -> * )之间的 morphism . 例子:
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 类型变量对于调用者来说是"inaccessible" . 因此,例如, sort :: Ord a => [a] -> [a] 不能成为自然变换,因为它是"picky"关于我们可以为 a 实例化哪些类型 . 我经常使用的一种直观方式是:
仿函数是一种在不触及结构的情况下对某些内容进行操作的方法 .
自然变换是一种在不触及或看内容的情况下对某事物的结构进行操作的方式 .
现在,让我们解决这个定义的条款 .
第一个子句是“endofunctor, T : X -> X ” . 好吧,Haskell中的每个 Functor 都是人们称之为"the Hask category,"的endofunctor,其对象是Haskell类型(种类 * ),其状态是Haskell函数 . 这听起来像一个复杂的陈述,但它实际上是一个非常微不足道的陈述 . 所有这意味着 Functor f :: * -> * 为您提供了为任何 a :: * 构建类型 f a :: * 的方法和任何 f :: a -> b 中的函数 fmap f :: f a -> f b ,并且这些函数遵守函子定律 .
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 f (Compose g h) ~= Compose (Compose f g) h
Compose f Identity ~= f
Compose Identity g ~= g
这些很容易证明,因为 Compose 和 Identity 都定义为 newtype ,而Haskell报告将 newtype 的语义定义为正在定义的类型与 newtype 's data constructor. So for example, let'的参数类型之间的同构证明 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.
709
注意:不,这不是't true. At some point there was a comment on this answer from Dan Piponi himself saying that the cause and effect here was exactly the opposite, that he wrote his article in response to James Iry' s . 但它似乎已被删除,可能是通过一些强迫性的整洁 .
以下是我原来的答案 .
Iry很有可能读过From Monoids to Monads,其中Dan Piponi(sigfpe)从Haskell的monoids中衍生monad,其中讨论了类别理论,并明确提到了“Hask上的endofunctors类别” . 无论如何,任何想知道monad在endofunctor类别中是monoid意味着什么的人都可能从阅读这个推导中受益 .
functor =>任何箭头,或两个类别之间的态射 (例如,日常 Tree a -> List b ,但在类别 Tree -> List )
monoid =>单个对象;即,单一类型,但在此上下文中,仅涉及外层;所以,我们不能有 Tree -> List ,只有 List -> List .
该语句使用"Category of..."这定义了语句的范围 . 例如,Functor类别描述 f * -> g * 的范围,即 Any functor -> Any functor ,例如 Tree * -> List * 或 Tree * -> Tree * .
分类声明未指定的内容描述了允许任何内容和所有内容的位置 .
在这种情况下,在仿函数内部,未指定 * -> * aka a -> b ,这意味着 Anything -> Anything including Anything else . 当我的想象力跳转到Int - > String时,它还包括 Integer -> Maybe Int ,甚至 Maybe Double -> Either String Int ,其中 a :: Maybe Double; b :: Either String Int .
所以声明如下:
仿函数范围 :: f a -> g b (即任何参数化类型的参数化类型)
endo仿函数 :: f a -> f b (即任何一个参数化类型为相同的参数化类型)...换句话说,
endofunctor类别中的monoid
那么,这个结构的力量在哪里?为了欣赏完整的动态,我需要看到一个monoid的典型图形(单个对象看起来像一个标识箭头, :: single object -> single object ),无法说明我被允许使用带有任意数量的monoid值参数化的箭头,来自Monoid中允许的一个类型对象 . endo,〜同义词的身份箭头定义忽略了仿函数的类型值以及最内层的"payload"层的类型和值 . 因此,等式在函数类型匹配的任何情况下返回 true (例如, Nothing -> Just * -> Nothing 等同于 Just * -> Just * -> Just * ,因为它们都是 Maybe -> Maybe -> Maybe ) .
边栏:〜外部是概念性的,但是 f a 中最左边的符号 . 它还描述了"Haskell"首先读入的内容(大图);所以类型是"outside"与类型值有关 . 编程中的层(参考链)之间的关系在类别中不易相关 . Set的类别用于描述类型(Int,Strings,Maybe Int等),其中包括Functor类别(参数化类型) . 参考链:Functor Type,Functor值(Functor集合的元素,例如Nothing,Just),以及每个functor值指向的其他所有内容 . 在类别中,关系的描述不同,例如, return :: a -> m a 被认为是从一个Functor到另一个Functor的自然转换,与目前为止提到的任何内容都不同 .
这经常被误解 . 该声明继续将 join :: m (m a) -> m a 描述为幺半群内向量的张量积 . 但是,它没有明确表示,在本声明的背景下,也可以选择 (<*>) . 它确实是一个六/半打的例子 . 组合 Value 的逻辑完全相同;相同的输入从每个输出生成相同的输出(与Int的Sum和Product monoids不同,因为它们在组合Ints时会产生不同的结果) .
那么,回顾一下:endofunctors类别中的monoid描述:
~t :: m * -> m * -> m *
and a neutral value for m *
(<*>) 和 (>>=) 都提供对两个 m 值的同时访问,以便计算单个返回值 . 用于计算返回值的逻辑完全相同 . 如果不是它们参数化的函数的不同形状( f :: a -> b 与 k :: a -> m b )和参数的位置具有相同的计算返回类型(即,分别为 a -> b -> b 与 b -> a -> b ),我怀疑我们可以参数化绰号逻辑,张量积,可在两种定义中重复使用 . 作为一个重点的练习,尝试并实现 ~t ,最终得到 (<*>) 和 (>>=) ,具体取决于您决定如何定义 forall a b .
5 回答
詹姆斯·伊里(James Iry)从他非常有趣的Brief, Incomplete and Mostly Wrong History of Programming Languages中得到了特别的措辞,他在虚构中将其归功于菲利普·瓦德勒(Philip Wadler) .
最初的引用来自Saunders Mac Lane的工作数学家类别,这是类别理论的基础文本之一 . Here it is in context,这可能是了解其含义的最佳地点 .
但是,我会采取刺 . 原句是这样的:
这里的X是一个类别 . Endofunctors是从类别到自身的仿函数(就函数式程序员而言,它通常都是
Functor
s,因为它们主要只处理一个类别;类型类别 - 但我离题了) . 但你可以想象另一个类别是“X上的endofunctors”类别 . 这是一个类别,其中对象是endofunctors,而态射是自然变换 .在那些终结者中,其中一些可能是单子 . 哪些是monad?正是那些在特定意义上是幺半群的 . 而不是拼写出从monad到monoids的确切映射(因为Mac Lane确实比我希望的要好得多),我只是将它们各自的定义并排放在一起,让你比较:
幺半群是......
一套, S
一个操作, • : S × S → S
S的元素, e : 1 → S
......满足这些法律:
(a•b)•c = a•(b•c),对于S中的所有a,b和c
e•a = a•e = a,对于S中的所有a
monad是......
一个endofunctor, T : X → X (在Haskell中,类型构造函数
* -> *
,带有Functor
实例)自然变换, μ : T × T → T ,其中×表示仿函数合成(μ在Haskell中称为join)
一个自然变换, η : I → T ,其中我是X上的标识endofunctor(η在Haskell中称为return)
......满足这些法律:
μ∘Tμ=μ∘μT
μ∘Tη=μ∘ηT= 1(身份自然变换)
稍微眯着眼睛,你可能会发现这两个定义都是同一个abstract concept的实例 .
直觉上,我认为花哨的数学词汇所说的是:
Monoid
monoid 是一组对象,以及组合它们的方法 . 众所周知的幺半群是:
您可以添加
个数字
你可以连接
列表
设置你可以结合
还有更复杂的例子 .
此外,每个monoid都有 identity ,这是"no-op"元素,当你将它与其他东西结合起来时没有效果:
0 7 == 7 0 == 7
[] [1,2,3] == [1,2,3] [] == [1,2,3]
{} union == union {} ==
最后,一个monoid必须是 associative . (只要你没有't change the left-to-right-order of objects) Addition is OK ((5+3)+1 == 5+(3+1)), but subtraction isn' t((5-3)-1!= 5-(3-1)),你可以随意减少一长串组合 .
Monad
现在,让我们考虑一种特殊的集合和一种组合对象的特殊方法 .
物体
假设您的集合包含特殊类型的对象: functions . 这些函数有一个有趣的签名:它们不会将数字带到数字或字符串中 . 相反,每个函数在两个步骤中将数字带到一个数字列表中 .
计算0或更多结果
以某种方式将这些结果合并为一个答案 .
例子:
1 - > [1](只需包装输入)
1 - > [](丢弃输入,将虚无包装在列表中)
1 - > [2](在输入中加1,并包装结果)
3 - > [4,6](在输入中加1,并将输入乘以2,并包装多个结果)
组合对象
另外,我们的功能组合方式很特别 . 组合函数的一种简单方法是组合:让我们看一下上面的例子,并用自己编写每个函数:
1 - > [1] - > [[1]](包装输入,两次)
1 - > [] - > [](丢弃输入,将虚无包装在列表中,两次)
1 - > [2] - > [UH-OH! ](我们不能"add 1"到列表!“)
3 - > [4,6] - > [UH-OH! ](我们不能添加1个列表!)
如果没有太多的类型理论,关键是你可以组合两个整数来得到一个整数,但你不能总是组成两个函数并获得相同类型的函数 . (类型为a - > a的函数将组成,但a-> [a]不会 . )
所以,让我们定义一种组合函数的不同方式 . 当我们结合其中两个函数时,我们不希望“双重包装”结果 .
这就是我们的工作 . 当我们想要组合两个函数F和G时,我们遵循这个过程(称为绑定):
从F计算"results"但不要合并它们 .
计算将G分别应用于F的每个结果的结果,得到一组结果集合 .
展平2级集合并合并所有结果 .
回到我们的例子,让我们使用这种“绑定”函数的新方法将一个函数与自身结合(绑定):
1 - > [1] - > [1](包装输入,两次)
1 - > [] - > [](丢弃输入,将列表中的虚无包裹两次)
1 - > [2] - > [3](添加1,然后再次添加1,并包装结果 . )
3 - > [4,6] - > [5,8,7,12](在输入中加1,并将输入乘以2,同时保留两个结果,然后对两个结果再次执行,然后换行最终结果列表 . )
这种更复杂的组合函数的方法是关联的(当你没有做出花哨的包装东西时,跟随函数组合是如何关联的) .
捆绑在一起,
monad是一种结构,它定义了一种组合(结果)函数的方法,
类似于monoid是一种定义组合对象的方式的结构,
组合方法是关联的,
并且有一个特殊的'No-op'可以与任何东西组合以产生不变的东西 .
注意事项
有很多方法可以“包装”结果 . 你可以制作一个列表,一个集合,或丢弃除第一个结果之外的所有结果,同时注意是否没有结果,附加状态的边车,打印日志消息等等 .
我对这些定义有点松散,希望能够直观地了解基本概念 .
我通过坚持我们的monad操作类型为a - > [a]的函数来简化了一些事情 . 事实上,monad在a - > m b类型的函数上工作,但是泛化是一种技术细节,而不是主要的洞察力 .
首先,我们将使用的扩展和库:
其中,
RankNTypes
是唯一对下面绝对必要的 . I once wrote an explanation of RankNTypes that some people seem to have found useful,所以我会参考 .引用Tom Crockett's excellent answer,我们有:
我们如何将其转换为Haskell代码?好吧,让我们从 natural transformation 的概念开始:
形式
f :-> g
的类型类似于函数类型,但不是将其视为两种类型(类型*
)之间的函数,而是将其视为两个 functors (各种类型* -> *
)之间的 morphism . 例子:基本上,在Haskell中,自然转换是从某种类型
f x
到另一种类型g x
的函数,这样x
类型变量对于调用者来说是"inaccessible" . 因此,例如,sort :: Ord a => [a] -> [a]
不能成为自然变换,因为它是"picky"关于我们可以为a
实例化哪些类型 . 我经常使用的一种直观方式是:仿函数是一种在不触及结构的情况下对某些内容进行操作的方法 .
自然变换是一种在不触及或看内容的情况下对某事物的结构进行操作的方式 .
现在,让我们解决这个定义的条款 .
第一个子句是“endofunctor, T : X -> X ” . 好吧,Haskell中的每个
Functor
都是人们称之为"the Hask category,"的endofunctor,其对象是Haskell类型(种类*
),其状态是Haskell函数 . 这听起来像一个复杂的陈述,但它实际上是一个非常微不足道的陈述 . 所有这意味着Functor f :: * -> *
为您提供了为任何a :: *
构建类型f a :: *
的方法和任何f :: a -> b
中的函数fmap f :: f a -> f b
,并且这些函数遵守函子定律 .第二个子句:Haskell中的
Identity
仿函数(随平台一起提供,所以你只需要导入它)就是这样定义的:因此,Tom Crockett定义的自然转换 η : I -> T 可以通过这种方式为任何
Monad
实例t
编写:第三个条款:Haskell中两个仿函数的组合可以通过这种方式定义(它也随平台一起提供):
所以汤姆克罗克特的定义中的自然变换 μ : T × T -> T 可以写成:
这是endofunctors类别中的monoid的语句意味着
Compose
(仅部分应用于其前两个参数)是关联的,Identity
是其标识元素 . 即,以下同构持有:Compose f (Compose g h) ~= Compose (Compose f g) h
Compose f Identity ~= f
Compose Identity g ~= g
这些很容易证明,因为
Compose
和Identity
都定义为newtype
,而Haskell报告将newtype
的语义定义为正在定义的类型与newtype
's data constructor. So for example, let'的参数类型之间的同构证明Compose f Identity ~= f
:注意:不,这不是't true. At some point there was a comment on this answer from Dan Piponi himself saying that the cause and effect here was exactly the opposite, that he wrote his article in response to James Iry' s . 但它似乎已被删除,可能是通过一些强迫性的整洁 .
以下是我原来的答案 .
Iry很有可能读过From Monoids to Monads,其中Dan Piponi(sigfpe)从Haskell的monoids中衍生monad,其中讨论了类别理论,并明确提到了“Hask上的endofunctors类别” . 无论如何,任何想知道monad在endofunctor类别中是monoid意味着什么的人都可能从阅读这个推导中受益 .
我通过更好地理解Mac Lane的工作数学家类别理论中臭名昭着的引用来推断这篇文章 .
在描述某些东西时,描述它不是什么通常同样有用 .
Mac Lane使用描述来描述Monad这一事实可能意味着它描述了monad特有的东西 . 忍受我 . 为了更广泛地理解这个陈述,我认为需要明确的是他并没有描述monad独有的东西;该声明同样描述了Applicative和Arrows等 . 出于同样的原因,我们可以在Int(Sum和Product)上有两个monoid,我们可以在endofunctors类别中的X上有几个monoid . 但是相似之处还有更多 .
Monad和Applicative均符合标准:
endo =>任何箭头,或在同一个地方开始和结束的态射
functor =>任何箭头,或两个类别之间的态射
(例如,日常
Tree a -> List b
,但在类别Tree -> List
)monoid =>单个对象;即,单一类型,但在此上下文中,仅涉及外层;所以,我们不能有
Tree -> List
,只有List -> List
.该语句使用"Category of..."这定义了语句的范围 . 例如,Functor类别描述
f * -> g *
的范围,即Any functor -> Any functor
,例如Tree * -> List *
或Tree * -> Tree *
.分类声明未指定的内容描述了允许任何内容和所有内容的位置 .
在这种情况下,在仿函数内部,未指定
* -> *
akaa -> b
,这意味着Anything -> Anything including Anything else
. 当我的想象力跳转到Int - > String时,它还包括Integer -> Maybe Int
,甚至Maybe Double -> Either String Int
,其中a :: Maybe Double; b :: Either String Int
.所以声明如下:
仿函数范围
:: f a -> g b
(即任何参数化类型的参数化类型)endo仿函数
:: f a -> f b
(即任何一个参数化类型为相同的参数化类型)...换句话说,endofunctor类别中的monoid
那么,这个结构的力量在哪里?为了欣赏完整的动态,我需要看到一个monoid的典型图形(单个对象看起来像一个标识箭头,
:: single object -> single object
),无法说明我被允许使用带有任意数量的monoid值参数化的箭头,来自Monoid中允许的一个类型对象 . endo,〜同义词的身份箭头定义忽略了仿函数的类型值以及最内层的"payload"层的类型和值 . 因此,等式在函数类型匹配的任何情况下返回true
(例如,Nothing -> Just * -> Nothing
等同于Just * -> Just * -> Just *
,因为它们都是Maybe -> Maybe -> Maybe
) .边栏:〜外部是概念性的,但是
f a
中最左边的符号 . 它还描述了"Haskell"首先读入的内容(大图);所以类型是"outside"与类型值有关 . 编程中的层(参考链)之间的关系在类别中不易相关 . Set的类别用于描述类型(Int,Strings,Maybe Int等),其中包括Functor类别(参数化类型) . 参考链:Functor Type,Functor值(Functor集合的元素,例如Nothing,Just),以及每个functor值指向的其他所有内容 . 在类别中,关系的描述不同,例如,return :: a -> m a
被认为是从一个Functor到另一个Functor的自然转换,与目前为止提到的任何内容都不同 .回到主线程,总而言之,对于任何已定义的张量积和中性值,该语句最终描述了一个由其矛盾结构产生的惊人强大的计算结构:
在外面它显示为单个对象(例如,
:: List
);静态的但在里面,允许很多动态
任何数量的相同类型的值(例如,Empty | ~NonEmpty)作为任何arity函数的饲料 . 张量积将把任意数量的输入减少到单个值...对于外层(~
fold
,它没有说明有效载荷)最内层的类型和值的无限范围
在Haskell中,澄清声明的适用性很重要 . 这种结构的强大功能和多功能性与monad本身完全无关 . 换句话说,构造不依赖于monad的独特之处 .
当试图弄清楚是否构建具有共享上下文的代码以支持相互依赖的计算时,与可以并行运行的计算相比,这个臭名昭着的语句,与其描述的一样,并不是选择应用,箭头和Monads,而是描述它们是多少相同 . 对于手头的决定,声明没有实际意义 .
这经常被误解 . 该声明继续将
join :: m (m a) -> m a
描述为幺半群内向量的张量积 . 但是,它没有明确表示,在本声明的背景下,也可以选择(<*>)
. 它确实是一个六/半打的例子 . 组合 Value 的逻辑完全相同;相同的输入从每个输出生成相同的输出(与Int的Sum和Product monoids不同,因为它们在组合Ints时会产生不同的结果) .那么,回顾一下:endofunctors类别中的monoid描述:
(<*>)
和(>>=)
都提供对两个m
值的同时访问,以便计算单个返回值 . 用于计算返回值的逻辑完全相同 . 如果不是它们参数化的函数的不同形状(f :: a -> b
与k :: a -> m b
)和参数的位置具有相同的计算返回类型(即,分别为a -> b -> b
与b -> a -> b
),我怀疑我们可以参数化绰号逻辑,张量积,可在两种定义中重复使用 . 作为一个重点的练习,尝试并实现~t
,最终得到(<*>)
和(>>=)
,具体取决于您决定如何定义forall a b
.如果我的最后一点至少在概念上是真的,那么它解释了Applicative和Monad之间的精确且唯一的计算差异:它们参数化的函数 . 换句话说,差异在于这些类型类的实现 .
总而言之,根据我自己的经验,Mac Lane臭名昭着的引用提供了一个伟大的“goto”模因,这是我在引导我的方式通过类别时引用的指南,以更好地理解Haskell中使用的习语 . 它成功地捕获了在Haskell中非常容易访问的强大计算能力的范围 .
然而,有点讽刺的是我第一次误解了陈述在monad之外的适用性,以及我希望在这里传达的内容 . 它所描述的一切都证明了Applicative和Monads(以及其他箭头)之间的相似之处 . 它没有说的正是它们之间的微小但有用的区别 .