[Haskell] Monad

class Monad m where
return :: a -> m a

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

(>>) :: m a -> m b -> m b
x >> y = x >>= \_ -> y

fail :: String -> m a
fail msg = error msg

Monad Law
（1）return x >>= f = f x
（2）m >>= return = m
（3）(m >>= f) >>= g = m >>= (\x -> f x >>= g)

注：
（1）:k m = * -> *
（2）在do notation中模式匹配失败后，程序并不会crash，而是会调用函数fail。
（3）m a类型的值，称为monad value。

（1）Maybe是Monad类型类的实例

instance Monad Maybe where
return x = Just x
Nothing >>= f = Nothing
Just x >>= f = f x
fail _ = Nothing

我们看一下>>=是如何实例化的

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

ghci> Just 9 >= \x -> return (x * 10)
Just 90

ghci> Nothing >>= \x -> return (x * 10)
Nothing

注：do notation

ghci> Just 3 >>= \x -> Just “!” >>= \y -> Just (show x ++ y)
Just “3!”

其中，

Just 3 >>= \x -> Just “!” >>= \y -> Just (show x ++ y)
= Just 3 >>= \x -> (Just “!” >>= \y -> Just ((show x) ++ y))
= Just 3   >>= \x ->
   Just “!” >>= \y ->
   Just (show x ++ y)
= do
   x <- Just 3
   y <- Just “!”
   Just (show x ++ y)

注：
（1）do表达式的结果是一个monad value。
（2）在do表达式中，如果某一行我们没有使用“<-”为monad value绑定值，就相当于使用了函数“>>”，表示不需要这个绑定值。（(>>) :: x >> y = x >>= \_ -> y）

do
    Just 1
    x <- Just 2
    Just x
= Just 1 >> Just 2 >>= \x -> Just x
= Just 1 >>= \_ -> Just 2 >>= \x -> Just x

（2）[]是Monad类型类的实例

instance Monad [] where
return x = [x]
xs >>= f = concat (map f xs)
fail _ = []

ghci> [1,2] >>= \n -> ['a','b'] >>= \ch -> return (n, ch)
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

推导如下：

[1,2] >>= \n -> ['a','b'] >>= \ch -> return (n, ch)
= concat $ map (\n -> ['a','b'] >>= \ch -> return (n, ch)) [1, 2]

(\n -> ['a','b'] >>= \ch -> return (n, ch)) 1
= ['a','b'] >>= \ch -> return (1, ch)
= concat $ map (\ch -> return (1, ch)) ['a','b']

(\ch -> return (n, ch)) 'a'
= return (1, 'a')
= [(1, 'a')]    （自动推导出类型`[(Int,Char)]`）

concat $ map (\ch -> return (1, ch)) ['a','b']
= concat [[(1, 'a')], [(1, 'b')]]
= [(1, 'a'), (1, 'b')]

concat $ map (\n -> ['a','b'] >>= \ch -> return (n, ch)) [1, 2]
= concat [[(1, 'a'), (1, 'b')], [(2, 'a'), (2, 'b')]]
= [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]

写成do notation如下：

[1,2] >>= \n -> ['a','b'] >>= \ch -> return (n, ch)
= do
n <- [1, 2]
ch <- ['a','b']
return (n, ch)

注： list comprehension

ghci> [(n, ch) | n <- [1, 2], ch <- ['a','b']]
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

所以，list comprehension只是do notation的语法糖。