Monad小记

Monad是函数式编程中的一个概念，对于函数式编程具有很重要的作用：实现纯函数无能为力的IO处理、在函数式编程中实现命令式编程。学习Monad主要的障碍是数学理论，其名称来源于范畴论中的一种数学结构。实际上函数式编程语言中的Monad也是根据这一结构来设计的。本文不展开讨论Monad的数学定义，而是讨论Monad在函数式编程语言Haskell中的定义和应用。

Haskell中的Monad⌗

class Monad m where
  return :: a -> m a
  (>>=) :: m a -> (a -> m b) -> m b

上述定义为Haskell中的定义，其中(>>=)亦被叫做bind（绑定函数）。

考虑一个简单的例子，作如下实现

data Optional a = Null | Present a deriving (Show)

对Optional进行操作的时候，需要这么写

  f :: (Num a) => Optional a -> Optional a -> Optional a -> Optional a
  f oa ob oc = case oa of
    Null        -> Null
    (Present a) -> case ob of
      Null        -> Null
      (Present b) -> case oc of
        Null        -> Null
        (Present c) -> Present (a * (b + c))

这么写非常的繁琐且丑陋。从代码的结构中，我们可以看到重复的东西，这些模式可以提取为共同的结构。考虑如下函数

  g oa f = case oa of
    Null        -> Null
    (Present a) -> f a

则f的定义可以改成

  f oa ob oc = g oa 
    $ \a -> g ob 
    $ \b -> g oc
    $ \c -> Present (a * (b + c))

再进一步，我们做一个约定-do记号

  do a <- ma
     fma a
  -- 等价于
  ma `g` fma

  do f
     do g
  -- 等价于
  do f 
     g

那么

  -- 第一步
  f oa ob oc = do a <- oa
                  g ob $ \b -> g oc
                       $ \c -> Present (a * (b + c))
  -- 第二步
  f oa ob oc = do a <- oa
                  b <- ob
                  g oc $ \c -> Present (a * (b + c))
  -- 第三步
  f oa ob oc = do a <- oa
                  b <- ob
                  c <- oc
                  Present (a * (b + c))

上述写法中，考虑函数g的定义，可以其和(>>=)一致。

 g :: m a -> (a -> m b) -> m b
 -- 等价于
 (>>=) :: m a -> (a -> m b) -> m b

考虑Monad中另一个函数的定义，应当有

return :: a -> m a
return = Present
-- 重写f
  f oa ob oc = do a <- oa
                  b <- ob
                  c <- oc
                  return (a * (b + c))
-- 可以把Optional实现为Monad
instance Monad Optional where
  return = Present
  (>>=) (Present a) f = f a
  (>>=) Null _ = Null
-- f的签名变成
f :: (Num a) => Optional a -> Optional a -> Optional a -> Optional a
f :: (Monad m, Num a) => m a -> m a -> m a -> m a

可以看出，Monad可用于简化函数式编程的代码，抽象出统一的结构。并且在一定程度上实现类似命令式编程的风格。最终的代码中，并未出现Optional本身的细节，因此Monad可以用来封装不纯的IO操作。Haskell中，IO实现了Monad的实例。do记号进一步简化了Monad的写法，使得开发人员能够直观上更好的理解代码的逻辑。同时Monad封装了上下文，使得环境变量通过上下文封装起来，不用出现在函数的参数列表中。进一步了解其他Monad，请参考All About Monad。常见的封装上下文的Monad有ReaderMonad、StateMonad等。

恒等式⌗

考虑如下do notation表示

  do { x <- return x; f x }    <=>    do {f x}

  do { x <- m ; return x }     <=>    do {m}

  do { y <- do {x <- m; f x}; g y}    <=>
  do { x <- m ; do { y <- f x ; g y}} <=>
  do { x <- m ; y <- f x ; g y}

这三组构造，从直觉上应当是相等的。然而若写成函数的形式，则表示如下

-- 左单元恒等式
  return >>= f  <=> f
-- 右单元恒等式
  m >>= return  <=> m
-- 结合律
  (m >>= f) >>= g <=> m >>= (\x -> f x >>= g) <=> m >>= f >>= g

很显然，这三组构造是有意义的，并且不能被推导。他们是Monad定义的一部分，实现的构造必须要满足这三组恒等式。否则上述do notation就没有意义了。

构造一个不满足条件的例子

data Count a = Count Int a

instance Monad Count where
  return = Count 1
  (>>=) (Count n a) f = let Count n' a' = f a in Count (n' + n) a'

可以来计算上述恒等式

-- 不满足左单元恒等式
  f n = Count 1 n
  (return >>= f) 1 = return 1 >>= f = f (Count 1 1) = Count 2 1
  f 1 = Count 1 1

可以证明上述恒等式在此例中均不成立。虽然要求满足三个恒等式，但是只要实现合理，一般地Monad的实现都能满足。此例中第二个类型参数是一个独立于Monad构造的简单累加器，其破坏了Monad构造的相等性。

副作用的表示⌗

计算机科学中，一个函数具有副作用是指在这个函数除了返回函数值之外，还影响函数作用域以外的状态或者被影响。


-- 作用域外的状态
   i = 3
   f n = n + i

-- 外部世界的状态
   g :: RealWorld -> a

上述函数中，若允许i可变，则函数f具有副作用；反之则没有副作用。函数式编程的模式中，由currying方法可以构造类似f函数的函数，如果允许i可变则可以使得这些函数的副作用消失；Haskell中不存在变量只存在绑定，因此，此类构造均为纯函数。

函数g的值由外部世界确定，因此其具有副作用。对于外部世界的处理，Haskell不能够通过取消变量来实现。其方案为使用Monad，因为其可以隐藏具体实现，而抽象出do notation。一个典型的IO Monad的构造如下

  IO = RealWorld -> (RealWorld,a)

外部世界被抽象成一个参数RealWorld，其表示了副作用的本征状态。对于涉及到外部世界的函数，则均需要通过IO来进行封装。这样就隔离了函数式编程中的纯函数和副作用函数，这种隔离区分对于实际编码会有很好的帮助。

Haskell Monad的等价定义⌗

Haskell Monad的正式定义中采用了return和(>>=)作为标准的定义，其原因和上一节的讨论有关系。数学中的Monad采用了另一种定义，return和join，他们的签名是

-- Monad in math
return :: a -> m a
join :: m (m a) -> m a

容易证明join和(>>=)是相互等价的

join = (>>= id)
-- 逆过程
(>>=) ma fma = join $ fmap fma ma
             = (>>= id) $ fmap fma ma
             = fmap fma ma >>= id  -- 此处涉及到fmap与>>=之间的关系
             = ma >>= id . return . fma
             = ma >>= fma

函数式编程语言最重要的设计模式为组合(compose)，其推广的数学结构为范畴。可以认为范畴就是研究函数的组合。那么对于Monad来讲，应当也可以设计组合。定义如下

  -- Kleisli范畴
  (>=>) :: (b -> m c) -> (a -> m b) -> (a -> m c)
  -- Kleisli函数的一般构造
  a -> m b

同样的，Kleisli范畴和Monad是等价的

  -- (>>=) -> (>=>)
  (>=>) fma fmb = \b -> fmb b >>= fma
  -- (>=>) -> join
  join = id >=> id
  -- 由于 (>>=) 和 join 相互等价，因此 (>=>)和它们也相互等价