引例#

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

#define NULL ((void*)0)

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

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

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

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

val a: Int? = 0

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

data  Maybe a  =  Nothing | Just a

假设有如下Kotlin定义

data class User(val name: String)

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

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

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

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

则实际完成了以下操作:

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

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

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

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

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

定义#

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

设$C$和$D$为范畴, 从$C$至$D$的函子为一映射$F$:

1. 将每个对象$X \in C$映射至一对象$F(X) \in D$上
2. 将每个态射$f:X\rightarrow Y \in C$映射至一态射$F(f):F(X) \rightarrow F(Y) \in D$上, 使之满足下列条件: 2.1. 对任何对象$X \in C$, 恒有${\displaystyle F(\mathbf {id} _{X})=\mathbf {id} _{F(X)}}$ 2.2. 对任何态射$f: X \to Y, \; g: Y \to Z$, 恒有$F(g \circ f) = F(g) \circ F(f)$.

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

以Maybe为例:

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

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

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

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

定义#

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

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函子需满足以下条件:

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实现:

instance Applicative Maybe where
    pure = Just

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

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

引例#

假设有如下Kotlin定义

data class User(val name: String?)

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

在Haskell中用Maybe来表示, 即

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

也就是

Maybe (Maybe String) === Maybe String

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

定义#

Monad在范畴论中定义如下:

${\displaystyle {\mathcal {C}}}$表示某范畴, ${\displaystyle {\mathcal {C}}}$上的单子是函子 ${\displaystyle T:{\mathcal {C}}\to {\mathcal {C}}}$, 连同两个自然变换, 分别是单位${\displaystyle \eta :1_{\mathcal {C}}\to T}$(其中${\displaystyle 1_{\mathcal {C}}}$是${\displaystyle {\mathcal {C}}}$上的恒等函子) 与乘法${\displaystyle \mu :T^{2}\to T}$(其中${\displaystyle T^{2}}$是复${\displaystyle T\circ T}$, 亦是${\displaystyle {\mathcal {C}}}$到${\displaystyle {\mathcal {C}}}$的函子), 且要满足下列连贯条件：

• ${\displaystyle \mu \circ T\mu =\mu \circ \mu T}$ (左右皆为 ${\displaystyle T^{3}\to T}$的自然变换). 此处 ${\displaystyle T\mu }$与 ${\displaystyle \mu T}$经水平复合而得.
• ${\displaystyle \mu \circ T\eta =\mu \circ \eta T=1_{T}}$ (两者皆为 ${\displaystyle T\to T}$的自然变换). 此处 ${\displaystyle 1_{T}}$表示由函子 $T$到自身的恒等自然变换.

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

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

与范畴论定义对应如下:

• return构造即为单位${\displaystyle \eta}$
• (>>=)函数为乘法${\displaystyle \mu}$
• ${\displaystyle \mu \circ T\mu =\mu \circ \mu T}$ 表示结合, 即 m >>= (\x -> k x >>= h) === (m >>= k) >>= h
• ${\displaystyle \mu \circ T\eta =\mu \circ \eta T=1_{T}}$ 表示左右单位, 即 m >>= return === m 和 return a >>= k === k a

Maybe的Monad可以如下实现:

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

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

a :: Maybe (Maybe String)
a = Just (Just "")

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

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

user :: Maybe User
user = Just User {name = Just ""}

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

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

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

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

List, 集合#

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, 错误处理#

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, 异步#

data Promise e a = Reject e | Resolve a