Warning: 硬核数学ahead
这些内容是其他教学不会教的，但是能大大增加你对函子和Monad的理解！里面也包含了不少我个人想出来的精华理解哦。
回顾集合的概念。在集合的范畴中，我们不仅讨论集合\(X,Y,\dots\)，还有集合之间的关系，即函数 \[ f: X\to Y \]
集合可以视作一类物件聚集在一起。但是集合本身并不会记住这些物件之间的关系。而范畴则可以看成一个“升级版”的集合（严格来讲范畴中的物件不需要构成一个集合，这是小范畴）。
我们说一个范畴(Category) \(\mathcal{C}\)是指以下信息：
里面有一类物件\(\mathrm{ob}(\mathcal{C})\)，是一个集合。通常直接把这个集合中的元素\(A\in \mathrm{ob}\mathcal{C}\) 简单记为\(A\in \mathcal{C}\).
对于每两个物件\(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)。
对于每三个物件\(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\]
这个合成满足结合律，\(1_A\)是该合成下的单位元。 \[ (f\circ g) \circ h = f \circ (g \circ h),\] \[ 1_A\circ f = f, \quad g\circ 1_A = g.\]
举例：
全体集合，以及集合之间的所有集合论函数，构成一个范畴\(\mathbf{Sets}\), 称为集合范畴。 其中的物件： \[\{1,2\},\varnothing, \mathbb{R}, \mathbb{Z},\{0,5,6\},\dots\] 其中的态射(箭头)： \[\{1,2\}\to \{\text{True},\text{False}\}, \varnothing\to A,\dots\]
全体\(k\)-向量空间，以及它们之间的所有线性函数，构成一个范畴\(\mathbf{Vect}_k\). \[0, V, W, \dots\] \[V\to W,\dots\]
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\xrightarrow{f} 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} \xrightarrow{F} \mathcal{D}\]
\[ A\mapsto F(A)\]
\[ (A\xrightarrow{f} B) \mapsto (F(A)\xrightarrow{F(f)} 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).
你可以将函子理解为一个升级版的映射，它不光把元素对应到元素，还把关系对应到关系。
我们可以将任何向量空间忘记掉向量空间的结构，退化成集合.这个对应关系是一个从\(\mathbf{Vect}_k\)到\(\mathbf{Sets}\)的函子，称为遗忘函子(Forgetful Functor)。这个函子会保持合成律，因为向量空间的映射和合成也必须先是集合上的映射和合成。
把\(\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\]
类似的，把类型\(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 aHom函子。\(\mathrm{Hom}(A, )\) 是一个从范畴\(\mathcal{C}\)到集合范畴\(\mathbf{Sets}\)的函子。它将物件\(B\)对应到集合\(\mathrm{Hom}(A,B)\),将态射\(B\xrightarrow{\alpha} C\) 对应到集合的映射 \[\mathrm{Hom}(A,B) \to \mathrm{Hom}(A,C) \] \[(A\xrightarrow{f} B) \mapsto \alpha\circ f=(A\xrightarrow{f} B \xrightarrow{\alpha} C)\] 它显然满足合成律，当有\(B\xrightarrow{\alpha} C\xrightarrow{\beta} D\)时： \[(\beta\circ\alpha)\circ f = \beta \circ (\alpha \circ f).\]
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事实上，在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)\xrightarrow{\eta_A} G(A)\xrightarrow{G(f)}G(B) \] \[ F(A)\xrightarrow{F(f)} F(B)\xrightarrow{\eta_B}G(B) \] 这两者作为\(\mathrm{Hom}_\mathcal{D}(F(A),G(B))\)中的元素相等。
在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 是一种从一个范畴到它自身的特殊的函子\(T:\mathcal{C}\to \mathcal{C}\)。我们首先注意到\(\mathcal{C}\)到自身的函子，是可以复合的，就像映射可以复合一样。如果在\(T\)上面定义了一种函子的’乘法’，将\(T\)到自身的两次复合合并成一次复合 \[\mu:T\circ T\Rightarrow T\] 并且这个’乘法’满足结合律 \[T^3 = T\circ(T\circ T) \xRightarrow{1_T\mu} T \circ T \xRightarrow{\mu} T\] \[T^3 = (T\circ T)\circ T \xRightarrow{\mu 1_T} T \circ T \xRightarrow{\mu} 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 \xRightarrow{\mu} T \] \[ T = T \circ 1_\mathcal{C} \xRightarrow{\mu} T \] 单位律要求这两者都与\(T\Rightarrow T\)的自然变换\(\mathrm{Nat}(T,T)\)中的\(1_T:T\Rightarrow T\),即什么也不干的恒等自然变换相等。
那么，我们就说\(T\)是一个Monad. 换而言之，一个Monad\(T\)是一个\(\mathcal{C}\)上的自函子，它需要带有两个自然变换 \[\mu:T^2\Rightarrow T,\quad \eta: 1\Rightarrow T\] 并且满足结合律和单位律。如果你知道什么是Monoidal category,这就是说Monad是Monoidal范畴\(\mathrm{End}(\mathcal{C})\)上的一个Monoidal object.
用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 T b\)变成 \(T a \to T^2 b\), 然后将它作用在\(T a\)上，最后使用乘法\(T^2 b \to T b\)得到\(T b\).
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 T a\), 只需将(>>=)中的类型变量a换成m a, b换成a即可得到
m (m a) -> (m a -> m a) -> m a
中间的映射m a -> m a 取恒等映射即可。
join = (>>= id)当\(\mathcal{C}\)上给定了一个Monad \(T\) 之后，我们可以考虑一个新的范畴\(K(\mathcal{C},T)\), 其中的物件和\(\mathcal{C}\)完全相同，但是态射由所有形如 \(a\to T b\) 的箭头(称之为Kleisli箭头)组成。范畴\(K(\mathcal{C},T)\)称之为Kleisli Category.
箭头的合成由下面的方法给出，如果我们有\(a \to T b\) 和\(b \to T c\), 那么我们可以先使用\(T\)的函子属性，得到一个箭头\(Tb \to T^2 c\), 然后使用\(T\)的Monad属性中的’乘法’自然变换\(\mu_c:T^2c\to Tc\), 将这两个箭头连接得到
\[ a\to Tb \xrightarrow{T(b\to Tc)} T^2 c\xrightarrow{\mu_c} Tc \]
这就是一个\(a\to T c\)的箭头。
也就是说我们得到了一个函数 \[\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 cnewtype 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 fabIO 是一个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.
类似的，我们注意到两次可能失败的动作可以合成一个可能失败的动作 \[\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} \; a \quad x \mapsto \mathrm{Just}\; x\]
return :: a -> Maybe a
return x = Just x两层\([[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]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 inputmain = 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.我们已经清楚的叙述了Monad的数学定义，Haskell中等价于给出 join 和 return, 也等价与给出 (>>=)和return. 但如果你需要在Haskell中定义Monad m, Haskell要求你先为m实现Functor class (这和我们预期的一致)和Applicative class(新概念！).
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要弱的概念。
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范畴是一种升级版的集合，它不仅记住了有哪些元素，还记住了这些元素之间的箭头和箭头的合成。
函子是一种升级的映射，它不仅要对应元素，还要对应箭头并且保持箭头之间的合成。Haskell中的函子映射由fmap 或者<$>统一给出。
Monad是一种特殊的自函子，它附带了两个自然变换，乘法\(\mu\)和单位\(\eta\)。需要满足结合律和单位律。在Haskell中写为join和return, 并且Haskell采用一个等价但不同的定义,使用binding operator (>>=)来替代乘法join.
IO, Maybe, [], Data.Map, (a ->) 都是Haskell中函子的例子。
IO, Maybe, [] 都是Haskell中Monad的例子。
在Haskell中，Monad自然的成为Applicative函子，并且在Haskell中你需要先定义Applicative才能定义Monad.