すごいH本が楽しかったのでまとめた

はじめに

入門書として『すごいHaskellたのしく学ぼう!』を読みました．
楽しく学んだので簡単にまとめました．
大事だと思った部分や躓いた部分をメインにまとめています．

再帰

関数定義の中で自分自身を呼び出しことを 再帰 と呼びます．
Haskellはとにかく再帰が多いので，頭を再帰に慣らしておくことが大事です．
クイックソートを例に説明した後，いくつかの再帰関数を見てみます．

クイックソート

まずはアルゴリズムを書き出します．

1. リストが空の場合，空リストを返す
2. それ以外の場合，リストの最初の要素 x を取り出す
3. x 以下の要素のリスト s と x より大きい要素のリスト l に分ける
4. s, l に対して手順1, 2, 3を適用する
5. 最後に全ての結果を結合する

具体例で試します．

[5, 1, 9, 4, 6, 7, 3]
[1, 4, 3] ++ [5] ++ [9, 6, 7]
([] ++ [1] ++ [4, 3]) ++ [5] ++ ([6, 7] ++ [9] ++ [])
([] ++ [1] ++ ([3] ++ [4] ++ [])) ++ [5] ++ (([] ++ [6] ++ [7]) ++ [9] ++ [])
([] ++ [1] ++ (([] ++ [3] ++ []) ++ [4] ++ [])) ++ [5] ++ (([] ++ [6] ++ ([] ++ [7] ++ [])) ++ [9] ++ [])
...
[1, 3, 4, 5, 6, 7, 9]

これを実際にコードに落とし込みます．

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let s = [a | a <- xs, a <= x]
        l = [a | a <- xs, a > x]
    in quicksort s ++ [x] ++ quicksort l

空のリストかどうかをパターンマッチで判定します．

quicksort [] = []
quicksort (x:xs) =

空でなかった場合は，先頭 x 以下の値を s に，x より大きい値を l に束縛します．

let s = [a | a <- xs, a <= x]
    l = [a | a <- xs, a > x]

最後に結果を返します．
このとき s, l に対して再帰的に関数を呼び出し，結果を結合しています．

in quicksort s ++ [x] ++ quicksort l

いくつかの再帰関数

再帰関数を考える時，まずはそれ以上分解できない 基底部 から考えるのがポイントです．

replicate

Int n と値 x を取り，x を n 回数繰り返したリストを返します．
基底部は，n が0回以下の場合は空リストを返します．
それ以外の場合は，x のheadと x を n-1 回繰り返したtailで構成されたリストを返します．

replicate' :: Int -> a -> [a]
replicate' n x
    | n <= 0    = []
    | otherwise = x : replicate' (n - 1) x

ghci> replicate' 3 5
[5, 5, 5]

take

リストから指定された個数 n の要素を返します．
n が0以下もしくはリストが空の場合は空リストを返します．
それ以外の場合は，リストを head x と tail xs に分解し，
x のheadと xs から n - 1 個取り出したtailで構成されたリストを返します．

take' :: Int -> [a] -> [a]
take' n _ |
    n <= 0     = []
take' _ []     = []
take' n (x:xs) = x : take' (n - 1) xs

ghci> take' 3 [5, 4, 3, 2, 1]
[5, 4, 3]

repeat

受け取った要素 x から無限リストを作ります．
基底部は存在しません．

repeat' :: a -> [a]
repeat' x = x : repeat' x

どのように評価されるか追ってみます．

repeat' 3
3 : repeat'3
3 : (3 : repeat' 3)
3 : (3 : (3 : repeat' 3))

評価は終了しないので，このままでは結果が返ってきません．
先ほどの take と組み合わせると replicate と同じような動作をします．

ghci> take 5 (repeat 3)
[3, 3, 3, 3, 3]
ghci> replicate 5 3
[3, 3, 3, 3, 3]

高階関数

Haskellの関数は，引数として関数を取ったり，戻り値として関数を返したりできます．
このような関数を 高階関数 と呼びます．

カリー化関数

1つの引数を取り，関数を返す関数を カリー化関数 と呼びます．
Haskellの全ての関数はカリー化されています．
max を例にとります．

ghci> max 4 5
5
ghci> :t max
max :: Ord a => a -> a -> a

シグネチャは Ord a => a -> (a -> a) と見ることができます．
これは，a 型の値を引数に取り，「a 型の値を引数にとり a 型の値を返す関数」を返す関数です．
関数がカリー化されていることで 部分適用 が可能になります．

ghci> let max' = max 4
ghci> :t max'
max' :: (Ord a, Num a) => a -> a
ghci> max' 5
5
ghci> max' 3
4

max' は a 型の値を引数に取り，a 型の値を返す関数です．
max の1つ目の引数に 4 がセットされた関数，といったイメージです．

いくつかの高階関数

map

関数とリストを引数に取り，リストのすべての要素に関数を適用したリストを返します．

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs

シグネチャは，a 型の値から b 型へ変換する関数と a 型の要素でできたリストを引数に取り，
b 型の要素でできたリストを返すことを表しています．
基底部は，空のリストを受け取った場合，空リストを返すよう定義しています．
それ以外の場合は，head x に f を適用した値とtail xs に対して f を再帰的に適用させた結果から
構成されたリストを返します．

ghci> map (*2) [1..5]
[2, 4, 6, 8, 10]
ghci> map (map (^2)) [[1, 2], [3, 4, 5], [6, 7, 8, 9]]
[[1, 4], [9, 16, 25], [36, 49, 64, 81]]

上記の例から，リストの各要素に対して関数を適用させたリストが返ってきているのが分かります．

filter

真偽値を返す関数とリストを引数に取り，True となる要素からなるリストを返します．

filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs)
    | p x       = x : filter p xs
    | otherwise = filter p xs

シグネチャは，a 型の値を判定して真偽値を返す関数と a 型の要素でできたリストを引数に取り，
a 型の要素でできたリストを返すことを表しています．
基底部は，空のリストを受け取った場合，空リストを返すよう定義しています．
それ以外の場合は，tail xs に対して再帰的に評価関数 p を適用させます．
このとき，head x に評価関数 p を適用した結果が真であれば x をheadとし，偽であれば x を捨てます．

ghci> filter even [1..5]
[2, 4]
ghci> filter (<=3) [1..5]
[1, 2, 3]

畳み込み

データ構造（例えばリスト）を単一の値にまとめるのに 畳み込み を使います．
畳み込み関数は，2引数関数とアキュムレータの初期値とリストを引数に取ります．
アキュムレータとリストの先頭（もしくは末尾）を2引数関数に渡し，
2引数関数から得られた結果が次のアキュムレータになります．
これをリスト全体を走査するまで繰り返します．

foldl

リストを左から順に畳み込みます．

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

シグネチャは，a -> b -> a なる2引数関数と a 型の値と b 型の要素でできたリストを受け取り，
a 型の値を返すことを表しています．
基底部は，空のリストを受け取った場合，単にアキュムレータ z を返すよう定義しています．
それ以外の場合では，アキュムレータ z とリストのhead x を関数 f に渡した結果を次のアキュムレータとし，
関数 f をアキュムレータとtail xs に再帰的に適用させます．
実際の例を使って動作を追ってみます．

foldl (+) 10 [1, 2, 3]
foldl (+) ((+) 10 1) [2, 3]
foldl (+) ((+) ((+) 10 1) 2) [3]
foldl (+) ((+) ((+) ((+) 10 1) 2) 3) []
((+) ((+) ((+) 10 1) 2) 3)
((+) ((+) 11 2) 3)
((+) 13 3)
16

foldr

リストを右から順に畳み込みます．
※ 走査自体は左から行われますが，関数適用が右から順に行われます．

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

シグネチャは，a -> b -> b なる2引数関数と b 型の値と a 型の要素でできたリストを受け取り，
b 型の値を返すことを表しています．
基底部は，空のリストを受け取った場合，単にアキュムレータ z を返すよう定義しています．
それ以外の場合では，関数 f の1番目の引数にリストのhead x を渡します．
2番目の引数には，関数 f をアキュムレータ z とtail xs に再帰的に適用させた結果を渡します．
実際の例を使って動作を追ってみます．

foldr (+) 10 [1, 2, 3]
(+) 1 (foldr (+) 10 [2, 3])
(+) 1 ((+) 2 (foldr (+) 10 [3]))
(+) 1 ((+) 2 ((+) 3 (foldr (+) 10 [])))
(+) 1 ((+) 2 ((+) 3 10))
(+) 1 ((+) 2 13)
(+) 1 15
16

mapを定義する

foldr を使って map を定義します．
空リストアキュムレータをとし，関数 f を適用させた結果とアキュムレータを結合します．

map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr (\x z -> f x : z) [] xs

実際の例を使って動作を追ってみます．

map' (+10) [1, 2, 3]
foldr (\x z -> (+10) x : z) [] [1, 2, 3] -- 以降 \x z -> (+10) x : z を f と置く
f 1 (foldr f [] [2, 3])
f 1 (f 2 (foldr f [] [3]))
f 1 (f 2 (f 3 (foldr f [] [])))
f 1 (f 2 (f 3 []))
f 1 (f 2 ((\x z -> (+10) x : z) 3 []))
f 1 (f 2 [13])
f 1 ((\x z -> (+10) x : z) 2 [13])
f 1 [12, 13]
(\x z -> (+10) x : z) 1 [12, 13]
[11, 12, 13]  

foldl を使って map を定義することもできます．

map' :: (a -> b) -> [a] -> [b]
map' f xs = foldl (\z x -> z ++ [f x]) [] xs

実際の例を使って追ってみます．

map' (+10) [1, 2, 3]
foldl (\z x -> z ++ [(+10) x]) [] [1, 2, 3] -- 以降 \z x -> z ++ [(+10) x] を g と置く
foldl g (g [] 1) [2, 3]
foldl g (g (g [] 1) 2) [3]
foldl g (g (g (g [] 1) 2) 3) []
g (g (g [] 1) 2) 3
g (g ((\z x -> z ++ [(+10) x]) [] 1) 2) 3
g (g [11] 2) 3
g ((\z x -> z ++ [(+10) x]) [11] 2) 3
g [11, 12] 3
(\z x -> z ++ [(+10) x]) [11, 12] 3
[11, 12, 13]

ただし，++ は : に比べて速度が遅いので，リストから新しいリストを生成する際は : を使用した方が良いです．

別の視点から見る畳み込み

リストに対する畳み込みは，以下のように見ることができます．
[3, 4, 5, 6] に対して初期値 z, 関数 f で畳み込みます．

-- 左畳み込み
f (f (f (f 3 z) 4) 5) 6

-- 右畳み込み
f 3 (f 4 (f 5 (f 6 z)))

2番目の引数を常に評価するとは限らない場合，右畳み込みは無限リストに対して動作します．

ghci> foldr (&&) True (repeat False)
False
ghci> foldl (&&) True (repeat False)
-- 返ってこない

このように書き出すと分かりやすいです．

False && (False && (False && (False ...

&& は1番目の引数が False の場合2番目の引数を評価せず結果を返すので正常に動作します．

(&&) :: Bool -> Bool -> Bool
True && x = x
False && _ = False

関数合成

. を使って，2つの関数を合成することができます．

(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)

シグネチャから分かるように，関数 g の戻り型と関数 f の引数の型は一致していなければ合成できません．
f (g (h x))) は (f . g . h) x と等価です．
関数合成を使うとスッキリ書くことができます．
ネストしたリストの各要素リストのtailの合計値の符号を反転させた値のリストを求めます．

ghci> map (\xs -> negate (sum (tail xs))) [[1..5], [3..6], [1..7]] -- without .
[-14, -15, -27]

ghci> map (negate . sum . tail) [[1..5], [3..6], [1..7]] -- with .
[-14, -15, -27]

奇数の平方数で 10000 より小さい値の総和は以下のように求める例でも，
関数合成を使ってみます．

ghci> sum . takeWhile (<10000) . filter odd $ map (^2) [1..]
166650

$ は単に関数を適用させるだけですが，最も低い優先順位を持っているため，
$ による関数適用は右結合となります．

($) :: (a -> b) -> a -> b
f $ x = f x

Functor

Functor は要素が変換可能な「箱」を表す型クラスです．
クラス定義は以下になります．

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

fmap は，「a 型から b 型への関数」と「a 型に適用されたファンクター値」を引数に取り，
「b 型に適用されたファンクター値」を返します．
これだけでは分からないので，リストと Maybe を例に見ていきます．

リスト

リストに対する Functor インスタンス宣言は以下のようになります．

instance Functor [] where
    fmap = map

fmap は各要素を与えられた関数で変換したリストを返します．

ghci> fmap (*) [1..3]
[2, 4, 6]
ghci> fmap even [1..3]
[False, True, False]

Maybe

Maybe は要素が0個か1個のリストのような値を表します．
失敗する可能性のある計算に対して Maybe を使うことができます．
要素が0個の値は Nothing，1個の値は Just で表します．

ghci> :m + Data.List
ghci> find (>3) [1..5]
Just 4
ghci> find (>10) [1..5]
Nothing

Maybe に対する Functor インスタンス宣言は以下のようになります．

instance Functor Maybe where
    fmap f Nothing  = Nothing
    fmap f (Just x) = Just (f x)

fmap は引数が Nothing なら Nothing を返します．
Just の場合は関数 f を中身の値 x に適用します．

ghci> fmap (*2) Nothing
Nothing
ghci> fmap (*2) (Just 3)
Just 6

Functor則

第1法則

恒等写像 id でファンクター値を写した場合，ファンクター値が変化してはいけない．
つまり，fmap id x と id x の結果は等しくなければなりません．
いくつか試してみます．

ghci> fmap id [1..5]
[1,2,3,4,5]
ghci> id [1..5]
[1,2,3,4,5]

ghci> fmap id Nothing
Nothing
ghci> id Nothing
Nothing

ghci> fmap id $ Just 3
Just 3
ghci> id $ Just 3
Just 3

第2法則

2つの関数 f と g について，
「f と g の合成関数でファンクター値を写したもの」と
「まず g，次に f でファンクター値を写したもの」は等しくなければならない．
つまり，fmap (f . g) x と fmap f $ fmap g x の結果は等しくなければなりません．
いくつか試してみます．

ghci> fmap ((+10) . (*3)) [1..3]
[13,16,19]
ghci> fmap (+10) $ fmap (*3) [1..3]
[13,16,19]

ghci> fmap ((+10) . (*3)) Nothing
Nothing
ghci> fmap (+10) $ fmap (*3) Nothing
Nothing

ghci> fmap ((+10) . (*3)) $ Just 3
Just 19
ghci> fmap (+10) $ fmap (*3) $ Just 3
Just 19

Maybe に対して第2法則が成り立っているか確認してみます．
まず Nothing から考えます．

fmap (f . g) Nothing
Nothing

fmap f $ fmap g Nothing
fmap f Nothing
Nothing

次に Just を考えます．

fmap (f . g) $ Just x
Just ((f . g) x)
Just (f (g x))

fmap f $ fmap g $ Just x
fmap f $ Just (g x)
Just (f (g x))

以上より，Maybe に対して第2法則が成り立っていることを確認できました．

Applicative

Applicative は要素に関数を持つ「文脈」を表す型クラスです．
クラス定義は以下になります．

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

pure は a 型の引数を取り，それをアプリカティブ値の中に入れて返します．
<*> は a -> b なる関数を要素に持つファンクター値と a 型のファンクター値を引数に取り，
b 型のファンクター値を返します．
Maybe とリストを例に見てみます．

Maybe

Maybe に対する Applicative のインスタンス宣言は以下のようになります．

instance Applicative Maybe where
    pure = Just
    Nothing <*> _ = Nothing
    (Just f) <*> something = fmap f something

pure は引数を Just に包んで返します．
<*> は1番目のファンクター値から取り出した関数 f を，2番目のファンクター値 something に fmap します．
いくつか試してみます．

ghci> Just (+3) <*> Just 9
Just 12
ghci> pure (+3) <*> Just 10
Just 13
ghci> Nothing <*> Just 2
Nothing

ghci> pure (+) <*> Just 2 <*> Just 3
Just 5
ghci> pure (\x y z -> x * y * z) <*> Just 2 <*> Just 4 <*> Just 10
Just 80

最後の例を追ってみます．

pure (\x y z -> x * y * z) <*> Just 2 <*> Just 4 <*> Just 10 -- 以降 \x y z -> x * y * z を f と置く
Just f <*> Just 2 <*> Just 4 <*> Just 10
fmap f (Just 2) <*> Just 4 <*> Just 10
Just (f 2) <*> Just 4 <*> Just 10
fmap (f 2) (Just 4) <*> Just 10
Just (f 2 4) <*> Just 10
fmap (f 2 4) (Just 10)
Just (f 2 4 10)
Just ((\x y z -> x * y * z) 2 4 10)
Just 80

pure は引数を Just に包んで返すので，pure x と Just x の動作は同じです．
<*> はファンクター値から取り出した関数を，次のファンクター値に適用します．
関数をデフォルトの文脈に入れてから適用する pure f <*> x は fmap f x と同じです．
そこで <$> を使います．

(<$>) :: (Functor f) => (a -> b) -> f a -> f b
f <$> x = fmap f x

先ほどの例が少し簡略化できます．

ghci> pure (+) <*> Just 2 <*> Just 3
Just 5
ghci> (+) <$> Just 2 <*> Just 3
Just 5

ghci> pure (\x y z -> x * y * z) <*> Just 2 <*> Just 4 <*> Just 10
Just 80
ghci> (\x y z -> x * y * z) <$> Just 2 <*> Just 4 <*> Just 10
Just 80

リスト

リストに対する Applicative のインスタンス宣言は以下のようになります．

instance Applicative [] where
    pure x = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]

pure は引数を単一要素のリストに入れて返します．
<*> は左辺のリストの中のそれぞれの関数を，右辺のリストの中の値に全ての組み合わせで適用させます．
いくつか試してみます．

ghci> [(+10), (*3), (^2)] <*> [1, 2, 3]
[11, 12, 13, 3, 6, 9, 1, 4, 9]
ghci> [(+), (*)] <*> [1, 2] <*> [3, 4]
[4, 5, 5, 6, 3, 4, 6, 8]

1つ目の例は [1, 2, 3] の各要素に対して，10を加えたもの，3倍したもの，2乗したものになります．
2つ目の例を追ってみます．

[(+), (*)] <*> [1, 2] <*> [3, 4]
[(1+), (2+), (1*), (2*)] <*> [3, 4]
[1 + 3, 1 + 4, 2 + 3, 2 + 4, 1 * 3, 1 * 4, 2 * 3, 2 * 4]
[4, 5, 5, 6, 3, 4, 6, 8]

Maybe 同様 <$> も使うことができます．

ghci> (*) <$> [2, 5, 10] <*> [8, 10, 11]
[16, 20, 22, 40, 50, 55, 80, 100, 110]

Applicative則

満たすべき法則を列挙します．

1. pure f <*> x = fmap f x
2. pure id <*> v = v
3. pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
4. pure f <*> pure x = pure (f x)
5. u <*> pure y = pure ($ y) <*> u

Maybeを例にざっと確認します．

第1法則

pure f <*> x = fmap f x

pure f <*> Just x -- 左辺
Just f <*> Just x
fmap f (Just x) -- 右辺

第2法則

pure id <*> v = v

pure id <*> Just x -- 左辺
Just id <*> Just x
fmap id (Just x)
Just (id x)
Just x -- 右辺

第3法則

pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

-- 左辺
pure (.) <*> Just f <*> Just g <*> Just x
Just (.) <*> Just f <*> Just g <*> Just x
fmap (.) (Just f) <*> Just g <*> Just x
Just (f .) <*> Just g <*> Just x
fmap (f .) (Just g) <*> Just x
Just (f . g) <*> Just x
fmap (f . g) (Just x)
Just ((f . g) x)
Just (f (g x))

-- 右辺
Just f <*> (Just g <*> Just x)
Just f <*> (fmap g (Just x))
Just f <*> Just (g x)
fmap f (Just (g x))
Just (f (g x))

第4法則

pure f <*> pure x = pure (f x)

pure f <*> pure x -- 左辺
Just f <*> Just x
fmap f (Just x)
Just (f x)
pure (f x) -- 右辺

第5法則

u <*> pure y = pure ($ y) <*> u

-- 左辺
Just f <*> pure x
Just f <*> Just x
fmap f (Just x)
Just (f x)

--右辺
pure ($ x) <*> Just f
Just ($ x) <*> Just f
fmap ($ x) (Just f)
Just (($ x) f)
Just (f x)

Monad

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

return は pure と同様，a 型の値を文脈に包んで返します．
>>= は a 型のモナド値と a -> m b なる関数を受け取り，b 型のモナド値を返します．
Maybe とリストを例に見てみます．

Maybeモナド

Maybe に対する Monad のインスタンス宣言は以下のようになります．

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

return は pure と同様，引数を Just に包んで返します．
>>= は左辺が Nothing なら Nothing を返します．
Just の場合は，中身の値 x に f を適用させます．
いくつか試してみます．

ghci> Just 9 >>= \x -> return (x + 10)
Just 19
ghci> Nothing >>= \x -> return (x + 10)
Nothing

もう少し遊んでみます．
引数を2倍し，10未満であれば Just で包んで返し，10以上であれば Nothing で返す maybeTwice を定義します．
>>= を使って maybeTwice を次々適用させます．

maybeTwice :: (Ord a, Num a) => a -> Maybe a
maybeTwice x =
    if twice < 10
        then return twice
        else Nothing
    where twice = 2 * x

ghci> Just 2 >>= maybeTwice
Just 4
ghci> Just 2 >>= maybeTwice >>= maybeTwice
Just 8
ghci> Just 2 >>= maybeTwice >>= maybeTwice >>= maybeTwice
Nothing

追ってみます．

Just 2 >>= maybeTwice >>= maybeTwice >>= maybeTwice
maybeTwice 2 >>= maybeTwice >>= maybeTwice
Just 4 >>= maybeTwice >>= maybeTwice
maybeTwice 4 >>= maybeTwice
Just 8 >>= maybeTwice
maybeTwice 8
Nothing

リストモナド

リストに対する Monad のインスタンス宣言は以下になります．

instance Monad [] where
    return x = [x]
    xs >>= f = concat $ map f xs

return は pure と同様，引数を単一要素のリストに入れて返します．
>>= は xs の各要素に f を適用して得られたネストしたリストを concat で平らにしています．
いくつか試してみます．

ghci> [1..3] >>= \x -> [x, -x]
[1,-1,2,-2,3,-3]
ghci> [] >>= \x -> [x, -x]
[]

追ってみます．

[1..3] >>= \x -> [x, -x]
concat $ map (\x -> [x, -x]) [1, 2, 3]
concat $ [[1, -1], [2, -2], [3, -3]]
[1, -1, 2, -2, 3, -3]

[] >>= \x -> [x, -x]
concat $ map (\x -> [x, -x]) []
concat []
[]

do記法

複数のモナド値を糊付けできるよう do記法 が用意されています．
文脈から中身の値を取り出しつつ，文脈の処理は >>= に任せることができます．
先ほどの maybeTwice を使って考えます．
成功するか失敗するのかの文脈処理は >>= に任せ，成功の場合は計算の途中結果すべてを返したいとします．

ghci> Just 2 >>= \x -> maybeTwice x >>= \y -> maybeTwice y >>= \z -> return [x, y, z]
Just [2, 4, 8]
ghci> Just 2 >>= \x -> maybeTwice x >>= \y -> maybeTwice y >>= \z -> maybeTwice z >>= \w -> return [x, y, z, w]
Nothing

できていますね．このラムダ式を書かなくていいようにdo記法を使います．

allTwice x = do
    y <- maybeTwice x
    z <- maybeTwice y
    return [x, y, z]

ghci> allTwice 2
Just [2, 4, 8]
ghci> allTwice 4
Nothing

途中の結果を束縛しながら文脈を処理できているのが分かりますね．

do記法はリストモナドにも適用できます．

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

ghci> listOfTuples
[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]

リスト内包表記はリストモナドの糖衣構文になっています．

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

Monad則

これまで通り Maybe を使って確認します．

左恒等性

return を使って値をデフォルトの文脈に入れたものを >>= で関数に食わせた結果は，
単にその値に関数を適用した結果と等しくなければなりません．

return x >>= f = f x

これは定義より明らかです．

return x >>= f -- 左辺
Just x >>= f
f x -- 右辺

右恒等性

モナド値を >>= を使って return に食わせた結果は，元のモナド値と等しくなければなりません．

m >>= return = m

Nothing と Just に分けて考えます．
これも定義より明らかです．

-- Nothing
Nothing >>= return -- 左辺
Nothing -- 右辺

-- Just
Just x >>= return -- 左辺
return x
Just x -- 右辺

結合法則

モナド関数適用の連鎖があるときに，どの順序で評価しても結果は等しくならなければなりません．

m >>= f >>= g = m >>= (\x -> f x >>= g)

-- Nothing 左辺
Nothing >>= f >>= g
Nothing >>= g
Nothing

-- Nothing 右辺
Nothing >>= (\z -> f z >>= g) -- 以降 \z -> f z >>= g を h と置く
Nothing >>= h
Nothing

-- Just 左辺
Just x >>= f >>= g
f x >>= g

--Just 右辺
Just x >>= (\z -> f z >>= g) -- 以降 \z -> f z >>= g を h と置く
Just x >>= h
h x
(\z -> f z >>= g) x
f x >>= g

おわりに

Haskellを楽しく学ぶことができました．
モナドについては理解できていない部分が多いので，
さらに勉強したらまたまとめようと思います．