Author: Eiko

Tags: Haskell, Haskell Magic, category theory, functor, monad, applicative, binding operator, natural transform, Kleisli category

Time: 2024-09-10 16:41:35 - 2024-09-10 16:41:35 (UTC)

Introduction to Haskell Magic - Lecture 4 基础的箭头魔法学(范畴论), 函子和Monad

Warning: 硬核数学ahead

这些内容是其他教学不会教的，但是能大大增加你对函子和Monad的理解！里面也包含了不少我个人想出来的精华理解哦。

箭头魔法学(基础范畴论)

回顾集合的概念。在集合的范畴中，我们不仅讨论集合$X,Y,\dots$，还有集合之间的关系，即函数 $$f:X\to Y$$

集合可以视作一类物件聚集在一起。但是集合本身并不会记住这些物件之间的关系。而范畴则可以看成一个“升级版”的集合（严格来讲范畴中的物件不需要构成一个集合，这是小范畴）。

我们说一个范畴(Category) $\mathcal{C}$是指以下信息：

1. 里面有一类物件$\mathrm{ob}(\mathcal{C})$，是一个集合。通常直接把这个集合中的元素$A\in \mathrm{ob}\mathcal{C}$ 简单记为$A\in \mathcal{C}$.

2. 对于每两个物件$A,B\in \mathcal{C}$, 有一个集合$\mathrm{Hom}(A,B)$，里面的元素是$f:A\to B$的所有箭头，称之为$A$到$B$的态射(Morphism)。并且所有$\mathrm{Hom}(A,A)$中都有一个典范的元素 $1_A:A\to A$, 称为恒等元或者单位元(identity)。

3. 对于每三个物件$A,B,C\in \mathcal{C}$, 有一个合成映射 $$\circ :\mathrm{Hom}(B,C)\times \mathrm{Hom}(A,B)\to \mathrm{Hom}(A,C)$$ $$(g,f)\mapsto g\circ f$$

4. 这个合成满足结合律，$1_A$是该合成下的单位元。 $$(f\circ g)\circ h=f\circ (g\circ h),$$ $$1_A\circ f=f,g\circ 1_A=g.$$

范畴是一种升级版的集合

举例：

1. 全体集合，以及集合之间的所有集合论函数，构成一个范畴$\mathbf{Sets}$, 称为集合范畴。 其中的物件： $$\{1,2\},\varnothing ,\mathbb{R},\mathbb{Z},\{0,5,6\},\dots$$ 其中的态射(箭头)： $$\{1,2\}\to \{\text{True},\text{False}\},\varnothing \to A,\dots$$

2. 全体$k$-向量空间，以及它们之间的所有线性函数，构成一个范畴${\mathbf{Vect}}_k$. $$0,V,W,\dots$$ $$V\to W,\dots$$

3. Haskell中全体基本类型，用户自定义类型，以及它们组合出来的类型，加上这些类型之间可以定义的函数，构成一个范畴$\mathbf{Hask}$.其中的物件： $$\mathbf{Int},\mathbf{Double},[\mathbf{Integer}],\mathbf{String},\mathrm{MyDataType}\mathbf{Int},(),\dots$$ 其中的态射(箭头)： $$(+1):\mathbf{Int}\to \mathbf{Int},\mathrm{print}:\mathbf{String}\to \mathbf{IO}(),\dots$$ 为了简单和让大家能够更容易理解，我们这里把这个范畴记作$\mathbf{Types}$.

范畴间的映射是函子

你可以简单理解为：范畴就是一个升级版的集合，它不光记住了一类物件，它还记住了这些物件之间的关系以及这些关系的复合。

既然集合$C,D$升级成了范畴$\mathcal{C},\mathcal{D}$，集合之间的映射$f:C\to D$也应该升级成“函子”，$F:\mathcal{C}\to \mathcal{D}$.

一个集合间的映射只需要将$C$中的任意物件$c\in C$对应到一个$D$中的物件$f(c)\in D$. 这是因为这些物件之间并没有任何关系，你可以随便怎么对应。 $$C\stackrel{f}{\to }D$$ $$c\mapsto f(c)$$

但是范畴中的物件是有箭头将它们联系起来的，因此一个函子不仅要把$\mathcal{C}$中的物件$C\in \mathcal{C}$对应到一个范畴$\mathcal{D}$中的物件$F(C)\in \mathcal{D}$,还要把$\mathcal{C}$中的箭头$f:A\to B$对应到$\mathcal{D}$中的箭头$F(f):F(A)\to F(B)$. $$\mathcal{C}\stackrel{F}{\to }\mathcal{D}$$

$$A\mapsto F(A)$$

$$(A\stackrel{f}{\to }B)\mapsto (F(A)\stackrel{F(f)}{\to }F(B))$$

并且这个对应过程不能破坏范畴的复合规则 $$F(g\circ f)=F(g)\circ F(f).$$ 注意左边的$g\circ f$是范畴$\mathcal{C}$中的复合，而右边的$F(g)\circ F(f)$则是范畴$\mathcal{D}$中的复合。

如果$F$满足上述要求，$F$就叫一个$\mathcal{C}\to \mathcal{D}$的函子(Functor), 或者协变函子(Covariant Functor).

如果$F$满足上述要求，但是合成律是相反的 $$F(g\circ f)=F(f)\circ F(g),$$ 那么$F$就叫一个反变函子(Contravariant Functor).

你可以将函子理解为一个升级版的映射，它不光把元素对应到元素，还把关系对应到关系。

函子的例子

1. 我们可以将任何向量空间忘记掉向量空间的结构，退化成集合.这个对应关系是一个从${\mathbf{Vect}}_k$到$\mathbf{Sets}$的函子，称为遗忘函子(Forgetful Functor)。这个函子会保持合成律，因为向量空间的映射和合成也必须先是集合上的映射和合成。

2. 把$\mathbf{Types}$中的任意类型$a$对应到$[a]$的对应过程是一个函子$\mathbf{Types}\to \mathbf{Types}$。首先对任意类型$a$都可以构造$[a]$，并且对任意类型间的函数$f:a\to b$我们都可以构造 $\mathrm{map}f:[a]\to [b]$, 这个过程会保持函数的合成： $$\mathrm{map}(f\circ g)=\mathrm{map}f\circ \mathrm{map}g$$

3. 类似的，把类型$a$对应到类型$\mathbf{Maybe}a$的过程是一个函子$\mathbf{Types}\to \mathbf{Types}$. 对任意类型$a$都可以构造$\mathbf{Maybe}a$, 并且当有映射$f:a\to b$时，我们可以构造映射 $\mathrm{maybeMap}f:\mathbf{Maybe}a\to \mathbf{Maybe}b$

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

它显然满足合成律

maybeMap (f . g) = maybeMap f . maybeMap g
-- both sides are Nothing if input is Nothing.
-- both sides are Just (f (g a)) if input is Just a

1. Hom函子。$\mathrm{Hom}(A,)$ 是一个从范畴$\mathcal{C}$到集合范畴$\mathbf{Sets}$的函子。它将物件$B$对应到集合$\mathrm{Hom}(A,B)$,将态射$B\stackrel{\alpha }{\to }C$ 对应到集合的映射 $$\mathrm{Hom}(A,B)\to \mathrm{Hom}(A,C)$$ $$(A\stackrel{f}{\to }B)\mapsto \alpha \circ f=(A\stackrel{f}{\to }B\stackrel{\alpha }{\to }C)$$ 它显然满足合成律，当有$B\stackrel{\alpha }{\to }C\stackrel{\beta }{\to }D$时： $$(\beta \circ \alpha )\circ f=\beta \circ (\alpha \circ f).$$

2. Haskell中的Hom函子。上一个例子也完全相同的出现在Haskell中，不同的是我们考虑的是$\mathbf{Types}$到自身的函子(a ->) :: Type -> Type, 这与$\mathrm{Hom}(A,)$的精神如出一辙。这个函子在映射上的作用就是合成.

homMap :: (a -> b) -> (c -> a) -> (c -> b) -- here the functor is (c ->)
homMap = (.) -- if you use eta reduction
-- homMap f g = f . g

Functor class

事实上，在Haskell中，这些Type Constructor都是函子：IO, Maybe, [], Data.Map, (a ->)… 在Haskell标准库中定义了如下Functor class: (这些函子都是协变函子)

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

    (<$>) = fmap -- the functor operator, they are identical functions.

这使得你只需要使用fmap就可以使用这些不同的函子。

safeSqrt :: Double -> Maybe Double
(*10) :: Double -> Double -- well, in fact (Num a) => a -> a
fmap (*10) :: Maybe Double -> Maybe Double -- well, in fact, (Functor f, Num a) => f a -> f a
fmap (*10) . safeSqrt :: Double -> Maybe Double

checkValidPassword :: String -> Maybe String

lengthPassword :: String -> Maybe Int
lengthPassword input = fmap length (checkValidPassword input)
                --   = length <$> (checkValidPassword input)

getLine :: IO String

fmap length getLine :: IO Int -- length :: String -> Int
length <$> getLine :: IO Int -- they are identical

-- in the number guessing game, we used some functor magic
readMaybe input :: Maybe Integer
compare :: (Ord a) => a -> a -> Ordering
compare secretNumber :: Integer -> Ordering
fmap (compare secretNumber) :: Maybe Integer -> Maybe Ordering

compare secretNumber <$> readMaybe input :: Maybe Ordering

函子范畴与自然变换

函子范畴，函子的态射是自然变换

值得注意的是，所有从范畴$\mathcal{C}$到范畴$\mathcal{D}$的函子构成的集合$\mathrm{Fun}(\mathcal{C},\mathcal{D})$本身也是一个范畴。这里面的物件是函子，而这里面的态射就叫自然变换(Natural Transform). 具体来说，取两个函子 $$F,G:\mathcal{C}\to \mathcal{D}$$ 一个从$F$到$G$的自然变换 $\eta :F\Rightarrow G$ 是指一族$\mathcal{D}$中的态射 $${\eta }_C:F(C)\to G(C)$$ 满足和函子本身的态射变化相兼容：当有$\mathcal{C}$中的态射$f:A\to B$时，我们会得到$F(f):F(A)\to F(B)$和$G(f):G(A)\to G(B)$,此时有 $$F(A)\stackrel{{\eta }_A}{\to }G(A)\stackrel{G(f)}{\to }G(B)$$ $$F(A)\stackrel{F(f)}{\to }F(B)\stackrel{{\eta }_B}{\to }G(B)$$ 这两者作为${\mathrm{Hom}}_{\mathcal{D}}(F(A),G(B))$中的元素相等。

Haskell中的自然变换

在Haskell中，函子f, g之间的自然变换应该是一族映射 f a -> g a, 对所有a都有定义(无限制的polymorphic function)。

natural :: FunctorF a -> FunctorG a

-- examples abound:
repeat :: a -> [a]  
-- this is a natural transform from 1_Types (identity functor) to [] (list functor).

tail :: [a] -> [a]
-- a natural transform from the list functor [] to itself.

const :: a -> (b -> a)
-- a natural transform from 1_Types to (b ->)

Monad

Monad 是一种从一个范畴到它自身的特殊的函子$T:\mathcal{C}\to \mathcal{C}$。我们首先注意到$\mathcal{C}$到自身的函子，是可以复合的，就像映射可以复合一样。如果在$T$上面定义了一种函子的’乘法’，将$T$到自身的两次复合合并成一次复合 $$\mu :T\circ T\Rightarrow T$$ 并且这个’乘法’满足结合律 $$T^3=T\circ (T\circ T)\stackrel{1_T\mu }{\Rightarrow }T\circ T\stackrel{\mu }{\Rightarrow }T$$ $$T^3=(T\circ T)\circ T\stackrel{\mu 1_T}{\Rightarrow }T\circ T\stackrel{\mu }{\Rightarrow }T$$ 结合律要求这两者作为$\mathrm{Fun}(T^3,T)$中的元素是相等的，并且这个乘法存在单位元$\eta$ $$\eta :1_{\mathcal{C}}\Rightarrow T$$ 这里$1_{\mathcal{C}}:\mathcal{C}\to \mathcal{C}$是什么也不干的恒等函子，满足乘法的单位律 $$T=1_{\mathcal{C}}\circ T\stackrel{\mu }{\Rightarrow }T$$ $$T=T\circ 1_{\mathcal{C}}\stackrel{\mu }{\Rightarrow }T$$ 单位律要求这两者都与$T\Rightarrow T$的自然变换$\mathrm{Nat}(T,T)$中的$1_T:T\Rightarrow T$,即什么也不干的恒等自然变换相等。

那么，我们就说$T$是一个Monad. 换而言之，一个Monad$T$是一个$\mathcal{C}$上的自函子，它需要带有两个自然变换 $$\mu :T^2\Rightarrow T,\eta :1\Rightarrow T$$ 并且满足结合律和单位律。如果你知道什么是Monoidal category,这就是说Monad是Monoidal范畴$\mathrm{End}(\mathcal{C})$上的一个Monoidal object.

Monad 使用 binding operator 的等价定义

用Haskell的语言来说，Monad的定义需要两个对a的类型无限制的Polymorphic函数(从而是范畴Types上的函子的自然变换)

join :: (Monad m) => m (m a) -> m a -- mu, the multiplication of the monad.

return :: (Monad m) => a -> m a  -- eta, unit of the monad

但是在Haskell中，大家对Monad的定义不是上述乘法(join)，而是一个连接运算符(>>=)

(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

可以证明，给出join和给出(>>=)是等价的，我们可以使用函子属性将 $a\to Tb$变成 $Ta\to T^{2}b$, 然后将它作用在$Ta$上，最后使用乘法$T^{2}b\to Tb$得到$Tb$.

ma >>= f  = join $ fmap f ma
-- or...
(>>=) = flip $ (join .) . fmap -- I spend 5 minutes trying to write this
-- equivalently,
(>>=) = fmap join . flip fmap
-- Challenge : can you understand these two expressions?
-- Hint:
-- fmap :: (a -> m b) -> m a -> m m b
-- join :: m m b -> m b
-- ((join .) .) :: (d -> c -> m m b) -> (d -> c -> m b)
-- (join .) . fmap :: (a -> m b) -> m a -> m b
-- flip is a standard function that swaps the two arguments of a two-variable function

反过来，如果给出了(>>=), 我们可以得到乘法$T^{2}a\to Ta$, 只需将(>>=)中的类型变量a换成m a, b换成a即可得到

m (m a) -> (m a -> m a) -> m a

中间的映射m a -> m a 取恒等映射即可。

join = (>>= id)

Kleisli Category

当$\mathcal{C}$上给定了一个Monad $T$ 之后，我们可以考虑一个新的范畴$K(\mathcal{C},T)$, 其中的物件和$\mathcal{C}$完全相同，但是态射由所有形如 $a\to Tb$ 的箭头(称之为Kleisli箭头)组成。范畴$K(\mathcal{C},T)$称之为Kleisli Category.

箭头的合成由下面的方法给出，如果我们有$a\to Tb$ 和$b\to Tc$, 那么我们可以先使用$T$的函子属性，得到一个箭头$Tb\to T^{2}c$, 然后使用$T$的Monad属性中的’乘法’自然变换${\mu }_c:T^{2}c\to Tc$, 将这两个箭头连接得到

$$a\to Tb\stackrel{T(b\to Tc)}{\to }{T}^{2}c\stackrel{{\mu }_c}{\to }Tc$$

这就是一个$a\to Tc$的箭头。

也就是说我们得到了一个函数 $$\mathrm{Hom}(a,Tb)\times \mathrm{Hom}(b,Tc)\to \mathrm{Hom}(a,Tc)$$ 用Haskell的语言来说，就是这样一个运算符：

(<=<) :: (Monad m) => (b -> m c) -> (a -> m b) -> a -> m c
-- the composition of Kleisli Arrows
-- Challenge : can you write the definition of (<=<) using join, in a pointless way?

-- we also have an opposite arrow
(>=>) :: (Monad m) => (a -> m b) -> (b -> m c) -> a -> m c

Monads in haskell

IO Monad

newtype IO a = IO a -- you are not allowed to use this constructor, though

-- IO a represents an action on the external world,
-- when completed, will return a value of type a

instance Functor IO where
    fmap fab (IO a) = -- wait for IO a return an value a , and then apply fab

IO 是一个Monad, 因为IO (IO a) 可以合成为一个IO a. 你可以想象一下，一个执行后会返回一个“执行后会返回a的动作”的动作，可以视为一个单独的，执行后会返回a的动作。这个过程是将两个动作合成为一个动作，这便是IO的乘法。

$${\mu }_a:\mathbf{IO}(\mathbf{IO}a)\to \mathbf{IO}a$$

这个乘法显然满足结合律，它的单位元是

$${\eta }_a:a\to \mathbf{IO}a$$

将一个类型为$a$的值包装成一个什么也不干，直接返回$a$的动作。

定义了这个乘法和单位之后，我们就可以得到IO 是一个Monad.

Maybe Monad

类似的，我们注意到两次可能失败的动作可以合成一个可能失败的动作 $${\mu }_a:\mathbf{Maybe}(\mathbf{Maybe}a)\to \mathbf{Maybe}a$$

你可以把Maybe a 想象成一个“薛定鄂”的盒子，里面可能装着类型a的物件(Just a)，也可能什么也没有(Nothing)。当我们有两个这样的盒子，一个套在另一个盒子外面的时候，我们可以把这两个盒子等效的合成为一个。当打开这两层的任意一层是Nothing的时候，我们就视为这个盒子给出了Nothing, 而两层都给出Just(Just a)时，我们就视为这个盒子给出了Just a. 这样我们就将两层Maybe 合为了一层。

join :: Maybe (Maybe a) -> Maybe a
join (Nothing)       = Nothing
join (Just Nothing)  = Nothing
join (Just (Just a)) = Just a

maybe >>= klei 
    = join $ fmap klei maybe
    = case maybe of
        Just a  -> klei a
        Nothing -> Nothing

乘法的单位是如下什么也不干，将一个确定的值装进盒子的映射：

$${\eta }_a:a\to \mathbf{Maybe}ax\mapsto \mathrm{Just}x$$

return :: a -> Maybe a
return x = Just x

List Monad

两层$[[a]]$可以通过concat合成为一层$[a]$, 这便给出了一个满足结合律的乘法 $${\mu }_a:[[a]]\to [a].$$

join :: [[a]] -> [a]
join = concat

list >>= klei 
    = join $ fmap klei list
    = concat (map klei list)

它的单位是把值包装为一个单元素的list的函数 $${\eta }_a:a\to [a]$$

return :: a -> [a]
return x = [x]

State Monad

Either s Monad

do-notation

Monad 的乘法和单位允许我们表达很多顺序计算和合成。由于结合律，我们还可以使用简洁又形象的do-notation来管理Monad的合成

main :: IO ()
main = getLine >>= (\input -> putStrLn input) -- or just getLine >>= putStrLn

-- equivalent way in do-notation
main = do 
    input <- getLine -- do notation is a syntax sugar, it is equivalent to the above
    putStrLn input

main = do
    putStrLn "name?"
    name <- getLine
    putStrLn "age?"
    age <- getLine
    putStrLn $ "Your name and age is" ++ show (name, age)

-- what the above really means is:
main = putStrLn "name?" >>= 
         (\_ -> getLine >>= 
           (\name -> putStrLn "age?" >>= 
             (\_ -> getLine >>= 
               (\age -> putStrLn ("Your name and age is " ++ show (name, age)) 
               )
             )
           )
         )


-- Luckily due to the associativity law of monad
-- (ma >>= famb) >>= fbmc = ma >>= (\a -> famb a >>= fbmc)
-- we do not have to write these parenthesis, 
-- i.e. 
putStrLn "name?" >>= ( \_ -> getLine >>= \name -> something ) 
= -- associativity law of monad guarantees that these are equal
( putStrLn "name?" >>= \_ -> getLine ) >>= \name -> something
-- and do-notation is well defined without specifying any parenthesis.

Define Monad in Haskell

我们已经清楚的叙述了Monad的数学定义，Haskell中等价于给出 join 和 return, 也等价与给出 (>>=)和return. 但如果你需要在Haskell中定义Monad m, Haskell要求你先为m实现Functor class (这和我们预期的一致)和Applicative class(新概念！).

Applicative 函子

class Functor f => Applicative f where
    pure  :: a -> f a  -- this is just the unit, or 'return'
    (<*>) :: f (a -> b) -> f a -> f b -- this allows you to apply a function value as a functor

我们先来说明一个Monad为什么自然的会成为一个Applicative函子.

(<*>) :: m (a -> b) -> m a -> m b
mf <*> ma = do
    f <- mf
    a <- ma
    return $ f a

-- or
mf <*> ma = mf >>= (\f -> ma >>= (\a -> return (f a)))

于是，Monad都是Applicative的，但是Applicative的则不一定是Monad.因此Applicative在Haskell中是一个比Monad要弱的概念。

例子：将Maybe定义为Monad

instance Functor Maybe where
    fmap f Nothing = Nothing
    fmap f (Just a) = f a

instance Applicative Maybe where
    pure = Just
    mf <*> ma = case mf of
        Just f -> case ma of
            Just a -> Just (f a)
            Nothing -> Nothing
        Nothing -> Nothing

instance Monad Maybe where
    return = pure
    ma >>= klei = case ma of
        Just a -> klei a
        Nothing -> Nothing

-- Now you can use do-notation to sequence chains of Maybe applications!

myCalculation :: String -> Maybe Double
myCalculation input = do
    x <- readMaybe input
    y <- safeSqrt x
    z <- safeSqrt (1 - y)
    return z

小结

1. 范畴是一种升级版的集合，它不仅记住了有哪些元素，还记住了这些元素之间的箭头和箭头的合成。

2. 函子是一种升级的映射，它不仅要对应元素，还要对应箭头并且保持箭头之间的合成。Haskell中的函子映射由fmap 或者<$>统一给出。

3. Monad是一种特殊的自函子，它附带了两个自然变换，乘法$\mu$和单位$\eta$。需要满足结合律和单位律。在Haskell中写为join和return, 并且Haskell采用一个等价但不同的定义,使用binding operator (>>=)来替代乘法join.

4. IO, Maybe, [], Data.Map, (a ->) 都是Haskell中函子的例子。

5. IO, Maybe, [] 都是Haskell中Monad的例子。

6. 在Haskell中，Monad自然的成为Applicative函子，并且在Haskell中你需要先定义Applicative才能定义Monad.