十木的博客

检书烧烛短，看剑引杯长

Functor and Monad

发表于 更新于

Functors

我们首先定义 fmap 函数，其功能类似于列表的 map。

其定义如下：

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

可以举几个例子：

列表：

1
2
3
instance Functor [] where
    -- fmap :: (a -> b) -> [a] -> [b]
    fmap = map

Maybe 类型：

1
2
3
instance Functor Maybe where
    fmap _ Nothing = Nothing
    fmap g (Just x) = Just (g x)

简单来说，fmap 就是对一个 Functor 类型的元素中的值进行操作。

fmap 需满足以下条件：

$$
\texttt{fmap id = id}
$$

$$
\texttt{fmap (g . h) = fmap g . fmap h}
$$

Applicatives

Functor 中 fmap 的参数只能是一元函数。而 Applicatives 提供了一种拓展：

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

这样，可以得到这样的结果：

1
2
3
4
5
6
7
8
fmap0 :: a -> f a
fmap0 = pure

fmap1 :: (a -> b) -> f a -> f b
fmap1 g x = pure g <*> x

fmap2 :: (a -> b -> c) -> f a -> f b -> f c
fmap2 g x y = pure g <*> x <*> y

在这里，<*> 类似于 -> 和 $，或者说是一种 Curry 化的方式。

当然，<*> 和 pure 也要满足一定的条件：

$$
\texttt{pure id <*> x = x}
$$

$$
\texttt{pure (g x) = pure g <*> pure x}
$$

$$
\texttt{x <*> pure y = pure (\g -> g y) <*> x}
$$

$$
\texttt{x <*> (y <*> z) = (pure (.) <*> x <*> y) <*> z}
$$

这些可能没有 Functor 的规则好理解。我们逐一解释：

  • $\texttt{pure id <*> x = x}$：保证 id 函数的恒等性质。

  • $\texttt{pure (g x) = pure g <*> pure x}$：两种 Curry 化传参数的方式对结果没有影响。

  • $\texttt{x <*> pure y = pure (\g -> g y) <*> x}$：交换参数顺序，函数不变。

  • $\texttt{x <*> (y <*> z) = (pure (.) <*> x <*> y) <*> z}$：这个是最复杂的一个，我们忽视 f 的存在，尝试用 -> 等来改写这个式子：

    $$
    \texttt{x -> (y -> z) = (x.y) -> z}
    $$

    其实不过是函数复合而已。

Monads

定义

我们先写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
data Expr = Val Int | Div Expr Expr

safediv :: Int -> Int -> Maybe Int
safediv _ 0 = Nothing
safediv n m = Just (n `div` m)

eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (Div x y) = case eval x of
    Nothing -> Nothing
    Just n -> case eval y of
        Nothing -> Nothing
        Just m -> safediv n m

这段代码是为了解决求解过程中出现除数为零的情况而产生的。然而这段代码一点也不简洁，与创造 Haskell 的大佬的理念不符。我们尝试使用刚刚学过的 Applicative：

1
2
3
eval :: Expr -> Maybe Int
eval (Val n) = pure n
eval (Div x y) = pure safediv <*> eval x <*> eval y

这段代码看起来不错，却有类型错误。函数将返回 Maybe (Maybe Int)。

可以看到类型对我们的限制还是很大的，如果不是因为类型错误，这段代码就非常理想了。而 Monad 恰恰可以帮我们解决这个问题：

1
2
3
4
5
6
7
8
9
10
class Applicative m => Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b
    return = pure

instance Monad Maybe where
-- (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
    mx >>= f = case mx of
        Nothing -> Nothing
        Just x -> f x

在这里定义的 >>= 运算符也相当于 $ 的作用，即 function application，然而它解决了此过程中 Maybe 的嵌套问题。

那么我们就可以如是定义 eval 函数：

1
2
3
4
5
eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (Div x y) = eval x >>= \n ->
                 eval y >>= \m ->
                 safediv n m

而 Monad 还提供了更简洁的实现（语法糖）：

1
2
3
4
5
eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (Div x y) = do n <- eval x
                    m <- eval y
                    safediv n m

你或许会疑心为什么这与 IO 中的 do 语句如此相似。事实上，IO正是 Monad 的实例：

1
2
3
4
5
6
instance Monad IO where
-- return :: a -> IO a
return x = ...

-- (>>=) :: IO a -> (a -> IO b) -> IO b
mx >>= f = ...

不过，这两个函数都是植入 Haskell 语言的，并不是通过 Haskell 后定义的，所以这里也没有他们的代码。在这里，当我们写出 c <- getChar() 这样的语句时，我们就将 IO Char 转化成了 Char。

Monad laws

我们同样列出 >>= 需要满足的条件：

$$
\texttt{return x >>= f = f x}
$$

$$
\texttt{mx >>= return = mx}
$$

$$
\texttt{(mx >>= f) >>= g = mx >>= (\x -> (f x >>= g)) }
$$

State monad

现在我们考虑一个问题：用函数描述状态的变化。

首先定义状态，我们以 Int 类型为例，并定义 state transformer（简写 ST）来表示一个对状态进行转化的函数。同时，状态的变化还可能产生结果，我们将这三样东西如下定义：

1
2
3
type State = Int
type ST = State -> State
newtype ST a = State -> (a, State) -- 为了方便后续将其声明为 Monad，我们这里使用 newtype

另外，我们定义作用函数：

1
2
app :: ST a -> State -> (a, State)
app (S st) x = st x

然后，我们先将其声明为 Functor，然后是 Applicative，最后是 Monad：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
instance Functor ST where
    -- fmap :: (a -> b) -> ST a -> ST b
    fmap g st = S (\s -> let (x, s') = app st s in (g x, s'))


instance Applicative ST where
    -- pure :: a -> ST a
    pure x = (\s -> (x, s))
    -- <*> = ST (a -> b) -> ST a -> ST b
    g <*> st = S (\s -> let (g', s') = app g s, (x, s'') = app st s' in (g' x, s''))


instance Monad ST where
    -- (>>=) :: ST a -> (a -> ST b) -> ST b
    st >>= f = S (\s -> let (x,s') = app st s in app (f x) s')

可以发现，我们定义的 <*> 是先将 g 作用于 s ，然后再用 st 作用于得到的状态。而 >>= 中则正好相反。事实上，<*> 的处理很容易理解，因为这符合我们一个一个传参数的顺序（也可以理解为上面的函数复合规则起的作用）。

Example: Relabelling trees

1
2
data Tree a = Leaf a | Node (Tree a) (Tree a)
    deriving (Show)

我们现在要给如上定义的树进行重新标号，让每一个叶子节点都有不同的自然数编号。我们写出朴素的方法：

1
2
3
4
5
6
rlabel :: Tree a -> Int -> (Tree Int, Int)
rlabel (Leaf _) n = (Leaf n, n+1)
rlabel (Node l r) n = (Node l' r', n'')
    where
        (l',n') = rlabel l n
        (r',n'') = rlabel r n'

现在我们用前面介绍的 State Monad 来改进这段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fresh :: ST Int
fresh = S (\n -> (n, n+1))

-- using the fact that it is an applicative functor
alabel :: Tree a -> ST (Tree Int)
alabel (Leaf _) = Leaf <$> fresh -- g <$> x = pure g <*> x
alabel (Node l r) = Node <$> alabel l <*> alabel r

-- using the fact that it is a monad
mlabel :: Tree a -> ST (Tree Int)
mlabel (Leaf _) = do n <- fresh        
    return (Leaf n)
mlabel (Node l r) = do l' <- mlabel l
    r' <- mlabel r
    return (Node l' r')

Generic function

我们现在在 Monad 上定义一些通用的函数。在 Control.Monad 中提供了此类函数的一些实现。

1
2
3
4
5
6
7
8
9
10
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
mapM f [] = return []
mapM f (x:xs) = do y <- f x
    ys <- mapM f xs
    return (y:ys)

join :: Monad m => m (m a) -> m a
join mmx = do mx <- mmx        
    x <- mx
    return x

范畴论相关

我们现在探究 Functor 和 Monad 在范畴论以及在 Haskell 中的关系：

Functor

范畴论中的 Functor 是两个范畴间的关系，对于 $F:C\to D$，它包括：

  • $\text{object-mapping }C_0\to D_0$

  • $\text{morphism-mapping operation }f_{c\to c’}\to g_{F \ c\to F\ c’}$

并满足以下条件：

  • $F\ 1_c = 1_{F \ c}$

  • $F\ (g \circ f)=F\ g \circ F \ f$

这很显然与 Haskell 中 Functor 的条件是一样的；事实上，Haskell 中定义的 Functor 的实例 $\texttt{f}$ 即是 $\text{object-mapping}$，$\texttt{fmap}$ 即是 $\text{morphism-mapping operation}$

Kleisli Category and Monad

对于一个范畴 $C$ 及其自函子 $m:C\to C$，定义其对应的 Kleisli Category $K$：

  1. $K_0\doteq C_0$

  2. $K_0\doteq {f_{a\to b}\ |\ f’_{a\to m \ b}\in C_1}$

  3. $\text{dom }f_{a\to b}\doteq a, \text{cod }f_{a\to b}\doteq b$

  4. $1_a\doteq\text{return}_{a\to m \ a}\in C_1$

  5. $g_{b\to c}\circ f_{a\to b}\doteq f’{a \to m \ b}\rightarrowtail g’{b\to m \ c} = h’_{a\to m \ c}$

条件：

  • $\text{Unit: }f\circ1=f=1\circ f$
  • $\text{Associativity: }h\circ(g\circ f)=(h\circ g)\circ f$

那么我们称 $m$ 为 Monad。那么我们可以如下定义 Monad:

1
2
3
class Monad m where
    (>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)
    return :: a -> m a

其中 >=> 运算符即是上述定义中的 $\rightarrowtail$。

当然，我们还可以进一步简化上述定义，比如前面介绍的 Haskell 中的 Monad 实践。