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


# はじめに

入門書として[『すごいHaskellたのしく学ぼう!』](https://www.amazon.co.jp/dp/4274068854/)を読みました．
楽しく学んだので簡単にまとめました．
大事だと思った部分や躓いた部分をメインにまとめています．


# 再帰

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

## クイックソート

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

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

具体例で試します．

```haskell
[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]
```

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

```haskell
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
```

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

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

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

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

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

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

## いくつかの再帰関数

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

### replicate

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

```haskell
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で構成されたリストを返します．

```haskell
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` から無限リストを作ります．
基底部は存在しません．

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

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

```haskell
repeat' 3
3 : repeat'3
3 : (3 : repeat' 3)
3 : (3 : (3 : repeat' 3))
```

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

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


# 高階関数

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

## カリー化関数

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

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

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

```haskell
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

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

```haskell
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` を再帰的に適用させた結果から
構成されたリストを返します．

```haskell
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` となる要素からなるリストを返します．

```haskell
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` を捨てます．

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

## 畳み込み

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

### foldl

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

```haskell
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` に再帰的に適用させます．
実際の例を使って動作を追ってみます．

```haskell
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

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

```haskell
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` に再帰的に適用させた結果を渡します．
実際の例を使って動作を追ってみます．

```haskell
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` を適用させた結果とアキュムレータを結合します．

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

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

```haskell
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` を定義することもできます．

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

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

```haskell
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` で畳み込みます．

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

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

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

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

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

```haskell
False && (False && (False && (False ...
```

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

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

## 関数合成

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

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

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

```haskell
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` より小さい値の総和は以下のように求める例でも，
関数合成を使ってみます．

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

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

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


# Functor

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

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

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

## リスト

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

```haskell
instance Functor [] where
    fmap = map
```

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

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

## Maybe

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

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

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

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

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

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

## Functor則

### 第1法則

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

```haskell
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` の結果は等しくなければなりません．
いくつか試してみます．

```haskell
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` から考えます．

```haskell
fmap (f . g) Nothing
Nothing

fmap f $ fmap g Nothing
fmap f Nothing
Nothing
```

次に `Just` を考えます．

```haskell
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` は要素に関数を持つ「文脈」を表す型クラスです．
クラス定義は以下になります．

```haskell
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` のインスタンス宣言は以下のようになります．

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

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

```haskell
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
``` 

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

```haskell
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` と同じです．
そこで `<$>` を使います．

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

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

```haskell
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` のインスタンス宣言は以下のようになります．

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

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

```haskell
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つ目の例を追ってみます．

```haskell
[(+), (*)] <*> [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` 同様 `<$>` も使うことができます．

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

## Applicative則

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

```haskell
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法則

```haskell
pure f <*> x = fmap f x
```

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

### 第2法則

```haskell
pure id <*> v = v
```

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

### 第3法則

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

```haskell
-- 左辺
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法則

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

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

### 第5法則

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

```haskell
-- 左辺
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` は，文脈付きの値と普通の値をとって文脈付きの値を返す関数渡し，
文脈付きの値を返すことを考えます．
クラス定義は以下になります．

```haskell
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` のインスタンス宣言は以下のようになります．

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

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

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

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

```haskell
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
```

追ってみます．

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

## リストモナド

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

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

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

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

追ってみます．

```haskell
[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` を使って考えます．
成功するか失敗するのかの文脈処理は `>>=` に任せ，成功の場合は計算の途中結果すべてを返したいとします．

```haskell
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記法を使います．

```haskell
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記法はリストモナドにも適用できます．

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

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

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

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

## Monad則

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

### 左恒等性

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

```haskell
return x >>= f = f x
```

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

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

### 右恒等性

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

```haskell
m >>= return = m
```

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

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

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

### 結合法則

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

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

```haskell
-- 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を楽しく学ぶことができました．
モナドについては理解できていない部分が多いので，
さらに勉強したらまたまとめようと思います．