一个单体只是内向量范畴中的一个单体,有什么问题吗?

谁首先说了以下的话?

一个单体只是一个单体在 内向量的范畴,有什么'的 问题?

还有一个不太重要的问题,这是不是真的,如果是的话,你能不能给一个解释(希望能让一个没有多少Haskell经验的人理解)?

解决办法

这句话是由James Iry提出的,来自他非常有趣的简短、不完整和大部分错误的编程语言史,他在其中虚构地将其归于Philip Wadler。

原文是Saunders Mac Lane在Categories for the Working Mathematician中的一段话,这是范畴理论的基础性文献之一。这里是它的上下文,这可能是了解它确切含义的最好地方。

不过,我还是要试一试。原句是这样的。

综上所述,X中的单体只是X的内向量类别中的一个单体,其中乘积×由内向量的组合取代,单位集由身份内向量取代。

这里X是一个范畴。内向量是指从一个类别到它本身的向量(就函数式程序员而言,这通常是*的 "向量",因为他们大多只处理一个类别;类型的类别--但我想说)。但你可以想象另一个类别,即X*上的内向量类别。这是一个对象为内向量、形态为自然变换的范畴。

而在这些内向量中,有些可能是单体。哪些是单体?正是那些在特定意义上是*单体的。我不打算说明从单体到单体的确切映射(因为麦克-莱恩在这方面做得比我好得多),我只是把它们各自的定义并排放在一起,让你来比较。

A monoid is...

*一个集合,*S**

  • 一个操作,*- : S × S → S**
  • 一个S的元素,*e : 1 → S**

...满足这些规律。

(a - b) - c = a - (b - c),对于S中的所有abce - a = a - e = a,对S中的所有a而言。

A monad是...

  • 一个内函数,T : X → X (在Haskell中,是一种* -> *的类型构造器,有一个Functor实例)
  • 一个自然转换,μ : T × T → T,其中×指的是漏斗组合(μ在哈斯克尔中被称为join)。
  • 一个自然转换,η : I → T,其中IX上的同一内向因子(η在哈斯克尔中被称为return)。

...满足这些规律。

μ ∘ Tμ = μ ∘ μTμ ∘ Tη = μ ∘ ηT = 1(同一自然变换)。

只要稍微眯一下眼睛,你也许就能看出这两个定义都是同一个抽象概念的实例。

评论(46)

直觉上,我认为花哨的数学词汇所表达的是:。

单子体

一个单体是一个对象的集合,以及组合它们的方法。著名的单体有

  • 数字,你可以添加
  • 你可以连接的列表
  • 可以联合的集合

还有更复杂的例子。

此外,每个单体都有一个特性,这就是那个"no-op"元素,当你把它和其他东西结合在一起的时候没有任何影响。

  • 0 + 7 == 7 + 0 == 7
  • [] ++ [1,2,3] == [1,2,3] ++ [] == [1,2,3] union {apple}*============={apple}union* {}

最后,一个单体必须是关联的。(只要你不改变对象的从左到右的顺序,你可以任意减少一长串的组合)加法是可以的((5+3)+1 == 5+(3+1)),但减法不是((5-3)-1 != 5-(3-1))。

单体

现在,让我们考虑一种特殊的集合和一种组合对象的特殊方式。

对象

假设你的集合包含一种特殊类型的对象。函数。而这些函数有一个有趣的特征。它们不把数字传给数字,也不把字符串传给字符串。相反,每个函数在一个两步过程中把一个数字带到一个数字列表中。

1.计算0个或更多的结果 2.将这些结果以某种方式组合成一个单一的答案。

举例说明。

  • 1 -> [1] (只是包住输入的内容)
  • 1 -> [](放弃输入,把虚无的东西包在一个列表中)。
  • 1 -> [2] (将1加到输入中,并将结果包起来)
  • 3 -> [4, 6](在输入的基础上加1,并将输入的结果乘以2,然后将*多的结果包起来

合并对象

另外,我们组合函数的方式也很特别。组合函数的一个简单方法是组合。让我们以上面的例子为例,将每个函数与自身进行组合。

  • 1 -> [1] -> [[1]] 。 (包住输入,两次)
  • 1 -> [] -> [] (放弃输入,将虚无的东西包在一个列表中,两次)
  • 1 -> [2] -> [UH-OH! ] (我们不能"把1"加到一个列表里!")。
  • 3 -> [4, 6] -> [ UH-OH! ] (我们不能在一个列表中添加1!)

在不涉及过多的类型理论的情况下,重点是你可以将两个整数结合起来得到一个整数,但你不能总是将两个函数组合起来得到一个相同类型的函数。(类型为a -> a的函数可以合成,但a-> [a]则不能。)

因此,让我们定义一种不同的组合函数的方式。当我们组合两个这样的函数时,我们不希望"double-wrap" 的结果。

我们的做法是这样的。当我们想结合两个函数F和G时,我们遵循这个过程(称为binding)。

1.计算F的"结果",但不结合它们。 2.2.分别计算将G应用于F'的每个结果的结果,产生一个结果集合的集合。 3.3.扁平化2级集合并合并所有的结果。

回到我们的例子,让我们用这种新的绑定函数的方式将一个函数和它自己结合起来(绑定)。

  • 1 -> [1] -> [1] (包住输入,两次)
  • 1 -> [] -> [] (放弃输入,将虚无的东西包在一个列表中,两次)
  • 1 -> [2] -> [3] (加1,然后再加1,把结果包起来。)
  • 3 -> [4,6] -> [5,8,7,12] (给输入加1,同时给输入乘以2,保留两个结果,然后对两个结果再做一次,然后把最后的结果包在一个列表中)。

这种更复杂的组合函数的方式关联性的(从当你不做花哨的包装时,函数组合是关联性的)。

把这一切联系起来。

  • 单体是一种结构,它定义了一种组合函数(结果)的方式。
  • 类似于单体是一种结构,它定义了一种组合对象的方式。
  • 其中组合的方法是关联的。 其中有一个特殊的'No-op',它可以与任何东西结合,导致东西*不变。

注释

有很多方法来"包装"结果。你可以做一个列表,或者一个集合,或者丢弃除第一个结果之外的所有结果,同时注意到是否没有结果,附加一个状态的副车,打印一个日志信息,等等。

我对定义做了一点松动,希望能直观地表达出基本的想法。

我通过坚持认为我们的单体对a -> [a]类型的函数进行操作来简化了一些事情。事实上,单体在a -> m b类型的函数上工作,但这种概括是一种技术细节,并不是主要的见解。

评论(6)

首先,我们要使用的扩展和库。

{-# LANGUAGE RankNTypes, TypeOperators #-}

import Control.Monad (join)

其中,RankNTypes'是唯一一个对下面的内容绝对必要的。[我曾经写过一篇关于RankNTypes'的解释,有些人似乎觉得很有用]1,所以我将参考一下。

引用Tom Crockett'的优秀答案,我们有。

A monad is...

  • 一个内函数,T : X -> X
  • 一个自然转换,μ : T × T -> T,其中×表示漏斗组成。
  • 一个自然转换,η : I -> T,其中IX上的同一内向因子。

...满足这些规律。

*μ(μ(T × T) × 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中的每个Functor都是人们称之为"Hask类别中的一个内函数,"其对象是Haskell类型(*类),其形态是Haskell函数。这听起来很复杂,但实际上是一个非常微不足道的声明。它的意思是说,一个Functor f ::* -> *给你提供了构造一个类型f a ::*为任何`a ::*"和一个函数 "fmap f :: f a -> f b "出来的任何 "f :: a -> b",并且这些都服从于向量法则。

第二条:Haskell中的Identity放函数(平台自带,所以你可以直接导入)是这样定义的。

newtype Identity a = Identity { runIdentity :: a }

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

所以Tom Crockett'的定义中的自然转换η : I -> T可以对任何单体实例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)

所以Tom Crockett'的定义中的自然变换μ : T × T -> T可以这样写。

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

这是一个内向量范畴的单体,这意味着 "组合"(部分应用于其前两个参数)是关联性的,并且 "同一性 "是其身份元素。也就是说,以下的同构关系成立。

  • Compose f (Compose g h) ~= Compose (Compose f g) h
  • 合成f的身份~= f
  • 组合身份g ~= g

这些都很容易证明,因为ComposeIdentity都定义为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.
评论(4)