猫不孤单
0%

Monad浅析

发表于
本文结合范畴论和Haskell语言, 浅要分析Monad(单子)

在Haskell中, 所有Monad都为Applicative函子, 而所有Applicative函子都为Functor, 即

1
2
3
class Applicative m => Monad m

class Functor f => Applicative f

因此, 要想了解Monad, 首先要了解Functor和Applicative.

Functor, 函子

引例

大多数语言拥有空概念, 表示不存在的值, 例如C中的NULL

1
#define NULL ((void*)0)

表示空指针, 可以转换为任意指针类型;

在Scala中, null表示空引用, 其类型为Null, 是任意引用类型的子类型, 所以null可以转换为任意引用类型:

1
2
val foo: Null = null 
val bar: SomeRefType = null

在Kotlin和Swift等语言中, 使用SomeType?标识可空类型, 例如

1
val a: Int? = 0

本质上, 可以为空的类型为空与任意类型的和类型, 在Haskell中实现为Maybe类型:

1
data  Maybe a  =  Nothing | Just a

假设有如下Kotlin定义

1
data class User(val name: String)

对于其实例user, 可以通过user.name访问name, 即

1
User -> String  // user.name 中的 "."

对于可空类型User?, 考虑safe call运算符?.,

1
val name = user?.name  // 从user中取出name, 否则返回null

则实际完成了以下操作:

1
Maybe User -> Maybe String  // user?.name 中的 "?."

也就是通过使用?.运算符将(User -> String)映射为(Maybe User -> Maybe String).

一般地, 对于任意函数(a -> b)都可以映射得到(Maybe a -> Maybe b), 以fmap表示, 则可以有如下实现:

1
2
3
fmap :: (a -> b) -> Maybe a -> Maybe b
fmap _ Nothing       = Nothing
fmap f (Just a)      = Just (f a)

Functor包含了对这种映射的抽象. 事实上, Maybe也是最简单的Functor.

定义

函子在范畴论中定义如下:

设和为范畴, 从至的函子为一映射:

  1. 将每个对象映射至一对象上
  2. 将每个态射映射至一态射上, 使之满足下列条件:
    2.1. 对任何对象, 恒有
    2.2. 对任何态射, 恒有.

换言之, 函子会保持单位态射与态射的复合.
一个由一范畴映射至其自身的函子称之为“自函子”.

以Maybe为例:

  • 1 即为构造 Just
  • 2 为函数 fmap
  • 2.1 表示不变 fmap id === id
  • 2.2 表示组合 fmap (f . g) === (fmap f) . (fmap g)

在Haskell中, Functor表示为类型类:

1
2
class Functor f where
    fmap :: (a -> b) -> f a -> f b

成为Functor需要满足条件2.1与2.2; 这里可以验证Maybe的上述fmap实现满足条件.

Applicative函子

假设有如下Kotlin定义

1
2
val f: ((A) -> B)? = null
val a: A? = null

那么将f施用给a会有点麻烦, 可以使用以下表达式:

1
val g: (A?) -> B? = { a -> a?.let { f?.invoke(it) }  }

完成((A) -> B)?到(A?) -> B?的映射, Applicative函子包含了对这种映射的抽象.

定义

Applicative是Functor和Monad的中间结构, 在Haskell标识为类型类:

1
2
3
class Functor f => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

pure将值装入Applicative, 对应Maybe即为Just;
(<*>)将装入Applicative的函数映射为装入Applicative中的值间的函数, 对应Maybe为Maybe (a -> b) -> Maybe a -> Maybe b

成为Applicative函子需满足以下条件:

1
2
3
4
pure id <*> v = v                            // 不变
pure (.) <*> u <*> v <*> w = u <*> (v <*> w) // 组合
pure f <*> pure x = pure (f x)               // 同态
u <*> pure y = pure ($ y) <*> u              // 交换

Maybe的Applicative实现:

1
2
3
4
5
instance Applicative Maybe where
    pure = Just

    Just f  <*> m       = fmap f m
    Nothing <*> _m      = Nothing

Applicative使函子拥有了将装入函子的函数应用给装入函子的值的能力.

Monad, 单子

引例

假设有如下Kotlin定义

1
data class User(val name: String?)

那么对于可空类型User?实例user, 调用safe call运算符“user?.name”时, 理论上会得到String??类型, 但是“可以为空的可空类型”理应与可空类型等价, 所以String??自动折叠为String?类型.

在Haskell中用Maybe来表示, 即

1
(Just a | Nothing) | Nothing === Just a | Nothing

也就是

1
Maybe (Maybe String) === Maybe String

但事实并非如此, Maybe (Maybe String) 与 Maybe String 是两种不同的类型; Monad则可以进行这种折叠操作, 或者避免出现这种嵌套类型.

定义

Monad在范畴论中定义如下:

表示某范畴, 上的单子是函子 , 连同两个自然变换,

分别是单位(其中是上的恒等函子)
与乘法(其中是复, 亦是到的函子), 且要满足下列连贯条件：

  • (左右皆为 的自然变换). 此处 与 经水平复合而得.
  • (两者皆为 的自然变换). 此处 表示由函子 到自身的恒等自然变换.

在Haskell中, Monad表示为类型类:

1
2
3
4
class Applicative m => Monad m where
    (>>=)       :: forall a b. m a -> (a -> m b) -> m b
    return      :: a -> m a
    return      = pure

与范畴论定义对应如下:

  • return构造即为单位
  • (>>=)函数为乘法
  • 表示结合, 即 `m >>= (\x -> k x >>= h) === (m >>= k) >>= h`
  • 表示左右单位, 即 `m >>= return === m` 和 `return a >>= k === k a`

Maybe的Monad可以如下实现:

1
2
3
instance  Monad Maybe  where
    (Just x) >>= k      = k x
    Nothing  >>= _      = Nothing

回到引例, 我们可以这样对Maybe (Maybe String)进行折叠:

1
2
3
4
5
a :: Maybe (Maybe String)
a = Just (Just "")

a' :: Maybe String
a' = a >>= id  // 常简写为join a

或者避免产生Maybe (Maybe String):

1
2
3
4
5
user :: Maybe User
user = Just User {name = Just ""}

name' :: Maybe String
name' = user >>= name

Monad是自函子范畴上的幺半群

半群

定义:
集合S和其上的二元运算·:S×S→S。若·满足结合律，即：∀x,y,z∈S，有(x·y)·z=x·(y·z), 则称有序对(S,·)为半群, 运算·称为该半群的乘法.
之所以称为半群, 是因为半群只满足群的部分性质.

在Haskell中, 半群用类型类Semigroup表示:

1
2
class Semigroup a where
    (<>) :: a -> a -> a

(<>)为半群的二元运算.

幺半群 (单位半群)

幺半群即含有幺元(单位元)的半群, 即: ∃e∈S，使得∀s∈S, e·s=s·e=s, 则S称为幺半群(独异点).

在Haskell中, 幺半群用Monoid表示:

1
2
class Semigroup a => Monoid a where
    mempty :: a

mempty为幺半群的单位元.

幺半群的例子

(Int, *) e = 1

1 * x == x * 1 == ×
(a * b) * c == a * (b * c)

(Int, +) e = 0

0 + x == x + 0 == x
(a + b) + c == a + (b + c)

(String, ++) e = “”

"" ++ x == x ++ "" == x
(a ++ b) ++ c == a ++ (b ++ c)

Monad幺半群

Monad的范畴论定义中, 若将当成幺半群的乘法, 则第一条公理类似幺半群的乘法结合律, 而第二条公理类似单位元的存在性(由 给出). 准确而言, 上的单子, 可以等价地定义为的内函子范畴中的幺半群. 如此, 单子不仅在形式上具有与幺半群相似的公理, 甚而单子就是幺半群的特例.

对于Haskell中的Monad, 其单位元为return, 乘法为(>>=):

  • 左单位元: m >>= return === m
  • 右单位元: return a >>= k === k a
  • 结合: m >>= (\x -> k x >>= h) === (m >>= k) >>= h

Monad例子

List, 集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
data List a = Nil | Cons a (List a)

instance Functor List where
    fmap _ Nil = Nil
    fmap f (Cons x xs) = Cons (f x) (fmap f xs)

instance Semigroup (List a) where
    Nil <> xs = Nil  
    Cons x xs <> ys = Cons x (xs <> ys)

instance Monoid (List a) where
    mempty = Nil

instance Applicative List where
    pure x = Cons x Nil
    Nil <*> _ = Nil
    _ <*> Nil = Nil
    Cons f fs <*> Cons x xs = Cons (f x) (fs <*> xs)

instance Monad List where
    Nil >>= f = Nil
    Cons x xs >>= f = f x <> (xs >>= f)

Result, 错误处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
data Result e a = Err e | Ok a

instance Functor (Result e) where
    fmap _ (Err e) = Err e
    fmap f (Ok a) = Ok (f a)

instance Applicative (Result e) where
    pure = Ok
    Err e <*> _ = Err e
    _ <*> Err e = Err e
    Ok f <*> Ok a = Ok (f a)

instance Monad (Result e) where
    Err e >>= k = Err e
    Ok a >>= k = k a

Promise, 异步

1
data Promise e a = Reject e | Resolve a

参考资料

https://zh.wikipedia.org/wiki/函子
https://zh.wikipedia.org/wiki/單子_(範疇論)
https://zh.wikipedia.org/wiki/半群
https://hackage.haskell.org/package/base-4.18.0.0/docs/src/GHC.Base.html