Code

来看几种基本 Monad

@Fallenwood 选修的 《Foundations of Programming Languages》 课程让我看的很手痒。整理一下基本的 Typeclass 和 Monad，准备跟随贵科步伐重新学习 Haskell。

  • 只做整理不做总结，绝不写任何有关自己对 Monad 的理解。

基本 Typeclass

Functor

  • Functor （Data.Functor）类型类表明型别可以被 map ，类型类声明为：
1
2
class Functor f where
  fmap :: (a -> b) -> f a -> f b
  • Functor 类型类定义中 f 的 kind 是 * -> *；<$> 是 fmap 的语法糖。
  • Functor 类型类需要遵守以下守则：
    • fmap id = id
    • fmap (f . g) = fmap f . fmap g

Applicative

  • Applicative （Control.Applicative）算是 Functor 的加强版，将一个 “包装” 在某个抽象型别中的函数应用到对应型别的值中，类型类声明为：
1
2
3
4
5
class (Functor f) => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b
  (<*) :: f a -> f b -> f a
  (*>) :: f a -> f b -> f b
  • Applicative 类型类中定义的型别 f 必须也是 Functor 类型类的实例。pure 函数将值包装到 Applicative Functor 中。<* 和 *> 函数均有默认实现。
  • 对于一个纯粹的函数 func :: a -> b，可以通过 fmap 将其作用到一个 Functor 类型类上，也可以通过 pure 将 func 提升到 Applicative Functor 中，再利用 <*> 将其运用到该类型类包装的值上。例如，pure (+) <*> (Just 2) <*> (Just 3) 的结果是 Just 5。可以利用 <$> 这一语法糖简化为 (+) <$> (Just 2) <*> (Just 3)。
  • Applicative 类型类需要遵守如下守则（必然也满足 Functor Laws）：
    • pure f <*> x = fmap f x
    • pure id <*> x = x
    • pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
    • pure f <*> pure x = pure (f x)
    • u <*> pure y = pure ($ y) <*> u

Monoid

  • Monoid （Data.Monoid）类型类的定义如下，它对应实例的型别 m 的 kind 是 *：
1
2
3
4
5
class Monoid m where
  mempty :: m
  mappend :: m -> m -> m
  mconcat :: [m] -> m
  mconcat = foldr mappend mempty
  • Monoid 指群论中的半群，其需满足封闭性和右结合律。Monoid 的名字看起来像是 mono 和 id 的组合，即 “单幺元”。这里的 mempty 和下面 MonadPlus 中的 mzero 均为幺元。
  • 几种常见的 Monoid 如： List、Any、All、Sum、Product、Ordering、Maybe 等。
  • Monoid 需要遵守如下守则：
    • mappend mempty x = x
    • mappend x mempty = x
    • mappend (mappend x y) z = mappend x (mappend y z)
  • Monoid 也应用在 Foldable 类型类的 foldMap 函数中。foldMap 的型别声明为 (Foldable t, Monoid m) => (a -> m) -> t a -> m。可以为自定义类型实作 Foldable 类型类，即可通过 foldMap 对自定义类型的元素做 map over、折叠等操作。注意 foldMap 和 fmap 的区别在于 foldMap 不会将函数返回值再次包装到原类型类中，而是包装到 Monoid 中。举个例子，对于自定义类型 data Tree a = Node a (Tree a) (Tree a) | Empty，要想确定树中有无小于 0 的元素，只需 getAny $ foldMap (\x -> Any $ x < 0) tree，这里 foldMap 把树中每个元素映射到 Any Monoid 中。

Monad

  • Monad （Control.Monad）类型类定义如下：
1
2
3
4
5
6
7
class Applicative m => Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  x >> y = x >>= \_ -> y
  return :: a -> m a
  fail :: String -> m a
  fail msg = error msg
  • Monad 的实例本身必须是 Applicative 的实例。其类型类定义中已经默认实现了 >> 和 fail，定义实例时可以重写这些函数，也可以只实现 return 和 >>=。return 等价于 pure。
  • 语法 do 可帮助把一些 Monad 操作连接在一起，其包裹的代码的每一行均为一个 Monad 实例的值。
  • List 的 Monad 实例定义如下：
1
2
3
4
instance Monad [] where
  return x = [x]
  xs >>= f = concat (map f xs)
  fail _ = []
  • 从 List 实例定义可看出，>>= 类似过程式语言中的循环嵌套，即将 >>= 左侧的 List 中的每个元素依次应用到右侧的函数上。List Comprehension 仅仅是它的语法糖，如 [x | x <- [1..10], xmod3 == 0] 等价于 [1..10] >>= \x -> if xmod3 == 0 then [x] else []。
  • Monad 需要遵守如下守则：
    • return x >>= f = f x
    • m >>= return = m
    • (m >>= f) >>= g = m >>= (\x -> f x >>= g)

MonadPlus

  • 上面的 List Comprehension 也等价于 [1..10] >>= \x -> guard (xmod3 == 0) >> return x。这需要用到 MonadPlus 类型类，它指同时表现为 Monoid 的 Monad，其定义为：
1
2
3
class Monad m => MonadPlus m where
  mzero :: m a
  mplus :: m a -> m a -> m a
  • mzero 等价于 mempty，mplus 等价于 mappend。 guard 函数的定义如下。当 guard 监察的 Bool 变量为 True 时，return 会返回一个空 unit，否则 在 List Comprehension 例子中，mzero = [] 不会产生任何结果。 
1
2
3
guard :: (MonadPlus m) => Bool -> m ()
guard True = return ()
guard False = mzero

常用 Monad

Writer

  • Writer （Control.Monad.Writer）的定义和 Monad 实例定义如下，该模块并未导出其值构造子。
1
2
3
4
5
newtype Writer w a = Writer { runWriter :: (a, w) }

instance (Monoid w) => Monad (Writer w) where
  return x = Writer (x, mempty)
  (Writer (x, v)) >>= f = let Writer (y, v') = f x in Writer (y, v `mappend` v')
  • 可用 tell 向 Writer 加入 log。

((->) r)

  • 函数也是 Monad，其实例为：
1
2
3
instance Monad ((->) r) where
  return = const
  g >>= f = \v -> f (g v) v

Reader

  • Reader （对函数 Monad 的一种包装）：
1
2
3
4
5
newtype Reader s a = Reader{ runReader :: s -> a }

instance Monad (Reader s) where
  return x = Reader (const x)
  m >>= k = Reader $ \r -> runReader (k (runReader m r)) r

State

  • State （Control.Monad.State）常用来表示状态迁移，代表了改变状态的操作：
1
2
3
4
5
6
7
newtype State s a = State{runState :: s -> (a, s)}

instance Monad (State s) where
  return x = State $ \s -> (x, s)
  (State h) >>= f = State $ \s -> let (a, newState) = h s
                                      (State  g) = f a
                                  in g newState

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(http://blog.forec.cn/2017/03/01/talk-about-some-simple-monads/) 、作者信息（Forec）和本声明。

分享到