Freeモナドのしくみ

Freeは、**Functorを受け取ってMonadをつくる**ことができるモナドです。

Freeのデータ型の定義は以下です。

```haskell:Freeの定義
data Free f a
  = Pure a
  | Free (f (Free f a))
```

よくわからない再帰的な定義がされていますね。初見で読めたらすごいと思います。

この記事では、上の定義のようなFreeが**どのようにMonadをつくるか**を見ていきます。

次のような順で説明していきます。

- PureScriptの予備知識と用語説明
- ListについてFunctor / Monadを実装する
- `Free f`について、同じようにFunctor / Monadを実装する

`Free f`だけでなく、Freeそれ自体もモナドではあるんですが、1つ高いレイヤー(誤魔化した言い方)でのモナドなのでこの記事では触れません。
PureScriptの型システムでは表現できないですしね。



# 忙しい人のためのFree

この記事で説明したいことをひとことで言うと、

- `Pure`が`pure`、`Free`が`join`の役割をするので、後は`map`があればMonadが実装できる

です。



# PureScriptの基本と用語の説明

この記事を読む人に必要があるのかはわかりませんが、さらっとだけ[^1]説明しておきます。

[^1]: の、予定だったんですが詳しく書きすぎてPureScript入門みたいになってしまいました……。

知っているという人は読み飛ばしても大丈夫です。
わからなくなったときに戻ってくる感じの読み方でもいいと思います。

PureScriptについて困ったときは公式のドキュメントとPursuitを見ましょう。

[purescript/documentation: Documentation for the PureScript language, compiler, and tools.](https://github.com/purescript/documentation)

[Pursuit](https://pursuit.purescript.org/)

Pursuitは本当によく使うので、"p"まで打つと出るようになってしまいました。

![スクリーンショット_2020-02-01_15-58-40.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/225715/bace6518-0784-9eb4-e1be-847d2f190fee.png)


## データ型の定義

データ型は、その型の値を生成する**値コンストラクタ**とよばれる関数の集まりとして定義されます。

```haskell:data構文
data <型名> <型引数1> <型引数2> ...
  = <値コンストラクタ名1> <引数1の型> <引数2の型> ...
  | <値コンストラクタ名2> <引数1の型> ...
  | ...
```

- `|`は値コンストラクタの区切り
- 型引数は0個以上
- 値コンストラクタの引数は0個以上 (引数なしの値コンストラクタ = 定数)
- 値コンストラクタは0個以上 (値コンストラクタがないデータ型 = 値を生成できないデータ型もつくれる)

```haskell:データ型の定義の例
data List a
  = Nil
  | Cons a (List a)
```

### 値コンストラクタ

`Nil`や`Cons`を**値コンストラクタ**とよびます。
その型の値を生成(construct)することに由来します。

また、**値コンストラクタは関数**です。

```haskell:値コンストラクタの型
-- List a型の定数
Nil :: forall a. List a

-- a型の値とList a型の値を受け取り、List a型の値を生成する関数
Cons :: forall a. a -> List a -> List a
```

`forall`については後ほど[関数の定義](#関数の定義)で説明します。

### 余談１：値コンストラクタと関数の違い

イメージは以下のようになります。

・通常の関数
関数適用`add 1 2` → `3`
定数`3` → これ以上評価できない

・値コンストラクタ
定数`Nil` → これ以上評価できない
関数適用`Cons 1 Nil` → **これ以上評価できない**

順に説明していきます。

`add 1 2`も`3`もPureScriptの式です。
また、これ以上評価できない式を値とよびます。[^2]

よって、定数`3`は**値**ですが、関数適用`add 1 2`は**値ではありません**。

[^2]: なんらかの意味での正規形 (Normal form) を値とよんでいます。用語が合っているのか自信がありません。

値コンストラクタでは少し異なります。

`Nil`は定数であり、これ以上評価できません。

問題は`Cons`ですが、
`Cons 1 Nil`
は関数適用ですが、**これ以上評価**できません。
つまり、**`Cons 1 Nil`は値**です。
文字通り、値コンストラクタは**値を生成する**ためです。

また、パターンマッチは値に対して使える機能です。

```haskell:パターンマッチの例
case xs of
  Nil -> ...
  Cons x xs -> ...

case n of
  0 -> ...
  1 -> ...
  _ -> ...
```

### 型コンストラクタ

`List Int`などの`List`を**型コンストラクタ**とよびます。
型を生成(construct)することに由来します。

また、「型の型」を、**カインド(kind、種)**とよびます。

`List`のように、型引数を取る型を**高カインド型**とよびます。

以下のような対応が考えられます。

|   | 引数なし | 引数あり |
|---|---|---|
| 値 | 定数 | 関数 |
| 型 | 型 | 高カインド型 |

PureScriptでは、**型のカインド**を表現する構文と**値の型**を表現する構文は同じなので、混同しないよう注意してください。

```haskell:値と型、型とカインドの対応
<値> :: <型>
<型> :: <カインド>
```

```haskell:値と型、型とかインドの例
-- <型 or 高カインド型 (型コンストラクタ)> :: <カインド>
List :: Type -> Type
List Int :: Type

-- <値 or 関数> :: <型>
Nil :: forall a. List a
Cons :: forall a. a -> List a -> List a
```

### ※値コンストラクタと型コンストラクタの混同

値コンストラクタと型コンストラクタは、たまに混同してしまうことがあります。

例として、二分木のデータ型`Tree`を考えます。

```haskell:値コンストラクタと型コンストラクタがややこしい例
data Tree a
  = Leaf a
  | Tree (Tree a) (Tree a)
```

このとき、
`Tree Int`
は、**型**であり、この`Tree`は**型コンストラクタ**です。

また、
`Tree (Leaf 0) (Leaf 1)`
は、**値**であり、この`Tree`は**値コンストラクタ**です。

`Tree a`などと書いてあると、これが型なのか、値なのか、文脈で判断するしかありません。
**型変数`a`を使った型**とも、**`Tree a -> Tree a`という型をもつ関数**とも見ることができるためです。

実際、
`Tree :: Tree a -> Tree a -> Tree a`
なので、
`Tree a :: Tree a -> Tree a`
となります。

`::`より前の`Tree a`は**関数**で、後ろに現れる`Tree a`は**型**です。
ややこしい……。


## 型クラスの定義と実装

型クラスは、ある型が満たすべき性質を定義します。

### 定義

```haskell:class構文1
class <型クラス名> <型変数> where
  <実装すべき関数名1> :: <関数1の型>
  <実装すべき関数名2> :: <関数2の型>
  ...
```

- 実装すべき関数は0個以上 (0個の場合、`where`も省略する)

```haskell:class構文1の例
class Functor f where
  map :: forall a b. (a -> b) -> f a -> f b
```

「(高カインド)型`f`がFunctorになるためには、関数`map`を実装する必要がある」と読めます。

型クラスは、型についても、高カインド型についても定義できます。

また、型クラスの定義には親子階層のような条件を付けられます。

```haskell:class構文2
class (<実装しているべき型クラス名1> <型変数>, <実装しているべき型クラス名2>, <型変数>, ...) <= <型クラス名> <型変数> where
  <関数名1> :: <関数1の型>
  <関数名2> :: <関数2の型>
  ...
```

- 実装しているべき型クラスは0個以上 (0個の場合、`(...) <=`は省略)

先ほど紹介した構文は、実際にはこの構文の満たすべき型クラスが0個の場合です。

```haskell:class構文2の例
class (Functor t, Foldable t) <= Traversable t where
  traverse :: forall a b m. Applicative m => (a -> m b) -> t a -> m (t b)
  sequence :: forall a m. Applicative m => t (m a) -> m (t a)
```

「(高カインド)型`t`がTraversableになるためには、`t`は型クラス`Functor`と`Foldable`を実装している必要があり、また関数`traverse`と`sequence`を実装する必要がある」と読めます。

`<=`は、逆向きで「ならば」と読めます。

`(Functor t, Foldable t) <= Traversable t`は「`t`が`Traversable`ならば、`t`は`Functor`であり、かつ`Foldable`である」と読めます。

「である」は「を実装している」の意味です。

関数の型定義の方の`=>`は、後ほど[関数の定義](#関数の定義)で説明します。

### 実装

```haskell:instance構文1
instance <インスタンス名> :: <実装する型クラス名> <型名> where
  <実装すべき関数名1> :: <関数1の型>
  <関数1の実装>
  ...
```

- インスタンス名はJavaScriptに変換した際のデバッグに使われる (ので、あまり気にしなくてもいい)
- 実装すべき関数が0個の場合は`where`以下を省略
- 型名の例：`Int`、`List`、`List Int`、`List a`

```haskell:instance構文1の例
instance functorList :: Functor List where
  map :: forall a b. (a -> b) -> List a -> List b
  map f Nil = Nil
  map f (Cons x xs) = Cons (f x) (map f xs)
```

ある型に対する型クラスの実装を、その型クラスの**インスタンス**とよびます。

「Listに対するFunctorのインスタンスを実装する」と読めます。[^3]
[^3]: これも用語が正確に合っているのか自信がありません。

これを少し雑に「ListにFunctorを実装する」と言っています。

また、型クラスの定義と同様に、型クラスの実装にも条件を付けることができます。

```haskell:instance構文2
instance <インスタンス名> :: <実装しているべき型クラス名1> <型変数n> => <実装しているべき型クラス名2> <型変数m> => ... => <型クラス名> <型名> where
  <関数名1> :: <関数1の型>
  ...
```

- 型変数は型名の中に現れるもの
- `=>`部分は0個以上

```haskell:instance構文2の例
instance eqList :: Eq a => Eq (List a) where
  eq = eq1
```

直感的な説明になりますが、ListはListの中身もまた比較可能である場合にのみ、比較することができます。
`eq1`は、Pursuitで見てもらうといいですが、今言ったような意味の型クラス`Eq1`で実装を課される関数です。

[Data.Eq - purescript-prelude - Pursuit](https://pursuit.purescript.org/packages/purescript-prelude/4.1.1/docs/Data.Eq#t:Eq1)


## 関数の定義

```haskell:関数の定義1
<関数名> :: forall <型変数1> <型変数2> ... . <型>
<関数名> <引数名1> <引数名2> ... = <実装>
```

```haskell:関数定義1の例
identity :: forall a. a -> a
identity x = x
```

「関数`identity`は、任意の型`a`について、`a -> a`という型をもち、実装は以下となる」と読めます。

`forall`は「任意の」と読めます。

また、`forall`の型変数に、型クラスの制約を付けることができます。

```haskell:関数定義2
<関数名> :: forall <型変数1> ... . <型クラス名1> <型変数n> => <型クラス名2> <かんた変数m> => <型>
<実装>
```

```haskell:例
elem :: forall a f. Foldable f => Eq a => a -> f a -> Boolean
-- 実装は省略
```

「関数`elem`は、任意の型`a`と`f`について、`f`がFoldableを実装していて、かつ`a`がEqを実装しているとき、`a -> f a -> Boolean`という型をもつ」と読めます。

`=>`は「ならば」「のとき」と読めます。

論理学の話になりますが、上で「かつ」と読んでいるのは、「A ⇒ B ⇒ C」は「A ∧ B ⇒ C」と読み替えることができるためです。

また、引数の型が複数の値コンストラクタをもつ場合、以下のような書き方ができます。

```haskell:例
length :: forall a. List a -> Int
length Nil = 0
length (Cons x xs) = 1 + (length xs)
```

Listは2つの値コンストラクタ、`Nil`、`Cons`をもちます。
また、値コンストラクタは値を生成するもの[^4]なので、パターンマッチが使えます。

[^4]: [余談１：値コンストラクタと関数の違い](#余談１値コンストラクタと関数の違い)で説明しています。

関数定義にも`where`があります。[^5]

[^5]: `where`は英語的な表現で、後出しで説明をするときに使います。「AはBである。ここで、BとはCである」みたいなとき、“A is B where B is C.”と書きます。

```haskell:例
append :: forall a. List a -> List a -> List a
append xs Nil = xs
append xs (Cons y ys) = append (snoc xs y) ys
  where
  snoc :: forall a. List a -> a -> List a
  snoc Nil y = (Cons y Nil)
  snoc (Cons x xs) y = Cons x (snoc y xs)
```

`where`には1個以上の関数が書けます。



# 長い前振りが終わった

ここまでが予備知識です。



# Listの例

`Free f`がMonadになることを見る前に、一般的なFunctor / Monadの実装について見ていきます。

具体的な例として、ListについてFunctor / Monadを実装してみます。

Listの定義は以下とします。

```haskell:Listの定義
data List a
  = Nil
  | Cons a (List a)
```


## List as Functor

Functorの定義は以下です。

```haskell:Functorの定義
class Functor f where
  map :: forall a b. (a -> b) -> f a -> f b
```

Functorは`Type -> Type`というカインドをもつ型に対する型クラスです。
「(高カインド)型`f`がFunctorになるためには、関数`map`を実装する必要がある」と読めます。

`map`は「関数`a -> b`をFunctorの関数`f a -> f b`に持ち上げる関数」と見ることができます。

Listでの実装は以下です。

```haskell:ListのFunctorインスタンス
instance functorList :: Functor List where
  map :: forall a b. (a -> b) -> List a -> List b
  map f Nil = Nil
  map f (Cons x xs) = Cons (f x) (map f xs)
```

とくに難しいところはないと思います。

ここで意識してほしいのは、`map`を実装するとき、使える関数は

- `Nil`、`Cons` (Listの値コンストラクタ)
- `map` (関数の再帰的な定義)
- 以上の関数を使って実装された関数

だけだということです。


## List as Applicative Functor

PureScriptでは、Applicative Functorはさらに細かくわけられます。

`Applicative m => Apply m => Functor m`

「Applicative FunctorであるならばApply」、「ApplyであるならばFunctor」と読めます。

Apply → Applicativeの順で実装していきます。

Applyの定義は以下です。

```haskell:Applyの定義
class (Functor m) <= Apply m where
  apply :: forall a b. m (a -> b) -> m a -> m b
```

「(高カインド)型`m`がApplyになるためには、`m`はFunctorである必要があり、また関数`apply`を実装する必要がある」と読めます。

`apply`は「Applyで包んだ関数を、Applyで包んだ値に適用する関数」と見ることができます。

Listでの実装は以下です。

```haskell:ListのApplyインスタンス
instance applyList :: Apply List where
  apply :: forall a b. List (a -> b) -> List a -> List b
  apply fs xs = concat (map (flip map xs) fs)
```

この実装は少し難しいです。
`map`と違い簡単に思いつきそうにはありません。

というわけで、型パズル[^6]の時間です。
[^6]: 本当は型を合わせるだけでは十分でないのですが、今回は考えないことにします。[余談２：Functor則 / Monad則](#余談２functor則--monad則)で説明しています。

型を見ることで、`apply`を実装する過程を見ていきます。

`apply`の実装に使えるのは、Functorの実装で触れた通り、

- `Nil`、`Cons`
- `apply`
- `map` (ListはすでにFunctorを実装しているため)
- 以上の関数を使って実装された関数

です。

上記の関数を使って`apply :: forall a b. List (a -> b) -> List a -> List b`を実装していきます。

それではレッツ型パズル！

```haskell:Apply_Listで型パズル1
-- Goal
apply :: List (a -> b) -> List a -> List b
apply fs xs = ...

-- 実装に使える関数
Nil :: List a
Cons :: a -> List a -> List a
map :: (a -> b) -> List a -> List b
apply :: List (a -> b) -> List a -> List b

-- applyの引数
fs :: List (a -> b)
xs :: List a

map :: (a -> b) -> List a -> List b
flip map :: List a -> (a -> b) -> List b
flip map xs :: (a -> b) -> List b
map (flip map xs) :: List (a -> b) -> List (List b)
map (flip map xs) fs :: List (List b)
```

※簡単のため`forall`を省略しています。ただし、`apply`の引数である`fs`と`xs`の型変数を読み換える際には注意が必要です。

※`flip`は関数の引数を入れ替える関数です。いきなり例外ですが、これはFunction型で実装された関数なので使えます。なくてもラムダ抽象を使えば同じ実装は可能です。

※`map :: (a -> b) -> List a -> List b`が「関数`a -> b`を関数`List a -> List b`に持ち上げる関数」であったことを思い出すとわかりやすいです。

ここで、`List (List b) -> List b`という型をもつ関数が欲しくなります。
ListのListをListにする関数なので、「中身のListをすべてつなげて1つのListにする関数」と考えられます。
この関数を`concat`とします。

```haskell:concatの実装
concat :: forall b. List (List b) -> List b
concat Nil = Nil
concat (Cons xs xss) = append xs (concat xss)
```

`append`は`List a -> List a -> List a`という型をもつ、2つのListをつなげる関数です。
[関数の定義](#関数の定義)の例として実装したので、わからない人は参照してください。

この`concat`を使って、`apply`を組み立てます。

```haskell:Apply_Listで型パズル2
map (flip map xs) fs :: List (List b)
concat :: List (List b) -> List b

concat (map (flip map xs) fs) :: List b

-- Goal
apply :: List (a -> b) -> List a -> List b
apply fs xs = concat (map (flip map xs) fs)
```

これで`apply`が実装できました。

型パズルすごい。

Applyが実装できたので、Applicativeを実装します。

```haskell:Applicativeの定義と、ListのApplicativeインスタンスの実装
class (Apply m) <= Applicative m where
  pure :: forall a. a -> m a

instance applicativeList :: Applicative List where
  pure :: forall a. a -> List a
  pure x = Cons x Nil
```

`pure`は値を1つ取って、Applicative Functorで包む関数です。


## List as Monad

PureScriptでは、Monadはさらに細かくわけられます。

`Monad m => (Applicative m, Bind m)`

`Bind m => Apply m`

「MonadであるならばApplicativeかつBind」、「BindであるならばApply」と読めます。

Bindの定義は以下です。

```haskell:Bindの定義
class (Apply m) <= Bind m where
  bind :: forall a b. m a -> (a -> m b) -> m b
```

「(高カインド)型mがBindになるためには、`m`はApplicativeかつBindである必要があり、また関数`bind`を実装する必要がある」と読めます。

Listでの実装は以下です。

```haskell:ListのBindインスタンスの実装
instance bindList :: Bind List where
  bind :: forall a b. List a -> (a -> List b) -> List b
  bind xs f = concat (map f xs)
```

型を見ることで、`bind`の実装を確かめてみます。

```haskell:bindの型の確認
concat :: List (List b) -> List b
map :: (a -> b) -> List a -> List b
xs :: List a
f :: a -> List b

map :: (a -> b) -> List a -> List b
-- bをList bで読み替える
map :: (a -> List b) -> List a -> List (List b)
map f :: List a -> List (List b)
map f xs :: List (List b)

concat (map f xs) :: List b

bind :: List a -> (a -> List b) -> List b
bind xs f = concat (map f xs)
```

大丈夫そうです。

Bindが実装できたので、Monadを実装します。

```haskell:Monadの定義と、ListのMonadインスタンスの実装
class (Applicative m, Bind m) <= Monad m

instance monadList :: Monad List
```

Monadは、ApplicativeとBindが実装されていれば他に実装するべき関数はありません。
`class`構文の`where`以下は省略されます。

`instance`構文でも同様です。

ここまででListにMonadを実装できました。



# Freeモナド

前置きが長くなりましたが、本題のFreeです。

FreeはFunctorを受け取り、`Free f`のような形でMonadになります。

Freeの定義は以下のような形をしています。

```haskell
data Free f a
  = Pure a
  | Free (f (Free f a))
```

Freeの型には、**`f`への制約がありません**。

代わりに、**型クラスの実装時に`f`がFunctorであることを課します**。
よって、`f`がFunctorのときのみ`Free f`はMonadになり、それ以外のときはMonadにはなりません。

それでは、`Free f`についてFunctor / Monadを実装していきます。


## Free as Functor

Functorの定義は以下です。

```haskell:Functorの定義
class Functor f where
  map :: forall a b. (a -> b) -> f a -> f b
```

`Free f`での実装は以下です。

```haskell
instance functorFree :: Functor f => Functor (Free f) where
  map f (Pure x) = Pure (f x)
  map f (Free x) = Free (map (map f) x)
```

`map`の実装は簡単には読めないと思います。
この実装がどこから出てきたのかというと、型パズルでひねり出しました。

まず、Freeには値コンストラクタが2つあったことを思い出します。
`Pure`と`Free`です。

それぞれ場合分けして考えます。

### `Pure x`のとき

```haskell:Functor_(Free_f)で型でパズル1
-- Goal
map f (Pure x) :: (a -> b) -> (Free f) a -> (Free f) b
map f (Pure x) = ...

-- 使える関数
Pure :: a -> Free f a
Free :: f (Free f a) -> Free f a
map :: (a -> b) -> f a -> f b

-- 引数の型
f :: a -> b
Pure x :: Free f a
```

※わかりやすいように`(Free f) a`としていますが、`Free f a`でも大丈夫です。

ここで、`Pure :: a -> Free f a`であることから、`Pure x`の`x`の型が`a`であることがわかります。

```haskell:Functor_(Free_f)で型パズル2
-- 使える関数
Pure :: a -> Free f a

-- mapの引数
f :: a -> b
x :: a

f x :: b
Pure (f x) :: Free f b

-- Goal
map :: (a -> b) -> Free f a -> Free f b
map f (Pure x) = Pure (f x)
```

こちらはあまり難しくないと思います。

問題は次です。

### `Free x`のとき

```haskell:Functor_(Free_f)で型パズル3
-- Goal
map f (Free x) :: (a -> b) -> Free f a -> Free f b
map f (Free x) = ...

-- 使える関数
Pure :: a -> Free f a
Free :: f (Free f a) -> Free f a
map :: (a -> b) -> Free f a -> Free f b
map :: (a -> b) -> f a -> f b

-- 引数の型
f :: a -> b
Free x :: Free f a
```

※`map`は`Free f`に対するものと、`f`に対するものがあります。`Free f`の`f`がFunctorでなければならない理由がここにあります。

また、`Pure x`のときと同様に、`Free :: f (Free f a) -> Free a`より、引数の`Free x`の`x`の型が`f (Free f a)`であることがわかります。

```haskell:Free型パズル4
-- 使える関数
Pure :: a -> Free a
Free :: f (Free f a) -> Free f a
map :: (a -> b) -> Free f a -> Free f b
map :: (a -> b) -> f a -> f b

-- 引数の型
f :: a -> b
x :: f (Free f a)

-- fに対するmapを使う
map :: (a -> b) -> f a -> f b
flip map :: f a -> (a -> b) -> f b
-- aをFree f aに読み替える
flip map :: f (Free f a) -> (Free f a -> b) -> f b
flip map x :: (Free f a -> b) -> f (Free f a)

-- Free f a -> bがほしい
-- Free fに対するmapを使う
map :: (a -> b) -> Free f a -> Free f b
map f :: Free f a -> Free f b

flip map x :: (Free f a -> b) -> f (Free f a)
-- bをFree f bで読み替える
flip map x :: (Free f a -> Free f b) -> f (Free f a)
flip map x (map f) :: f (Free f a)
-- flipを外す
map (map f) x :: f (Free f a)

Free (map (map f) x) :: Free f a

-- Goal
map :: (a -> b) -> Free f a -> Free f b
map f (Free x) = Free (map (map f) x)
```

これで`map`が実装できました。

この型パズルを解くのは結構楽しいので、以降のApplicative FunctorとMonadの型パズルは答えを見る前にやってみると面白いかもしれません。

ただ「できた！」と思ったら`map f (Free x) = map f (Free x)`になっていた、みたいなことが数回あったのでみなさんはそうはならないよう気を付けてください。


## Free as Applicative Functor

PureScriptでは

`Applicative m => Apply m => Functor m`

となっているので、Applyから実装していきます。

Applyの定義は以下です。

```haskell:Applyの定義
class (Functor m) => Apply m where
  apply :: forall a b. m (a -> b) -> m a -> m b
```

`Free f`での実装は以下です。

```haskell:Free_fのApplyインスタンス
instance applyFree :: Functor f => Apply (Free f) where
  apply :: Free f (a -> b) -> Free f a -> Free f b
  apply (Pure f) (Pure x) = Pure (f x)
  apply (Free f) (Pure x) = Free (map (flip apply (Pure x)) f)
  apply f (Free x) = Free (map (apply f) x)
```

`map`のときとは異なり、`apply`の引数では関数も`Free f`で包まれています。
よって、値コンストラクタでの場合分けが4パターンになります。

ただし、上の実装の通り実際には3パターンに潰せます。

型パズルは省略します。
実装に疑いのある人は各自で確認してみてください。

Applyが実装できたので、Applicativeを実装します。

```haskell:Applicativeの定義とFree_fのApplicativeインスタンスの実装
class (Apply m) => Applicative m where
  pure :: forall a. a -> m a

instance applicativeFree :: Functor f => Applicative (Free f) where
  pure = Pure
```

`pure`の実装は値コンストラクタそのままです。

ただし、「`pure = Pure`となっている」ということはとても重要な事実になります。
[直感的な説明](#直感的な説明)で後ほど説明します。


## Free as Monad

PureScriptでは

`Monad m => (Applicative m, Bind m)`

`Bind m => Apply m`

となっているので、Bindから実装していきます。

Bindの定義は以下です。

```haskell:Bindの定義
class (Apply m) => Bind m where
  bind :: forall a b. m a -> (a -> m b) -> m b
```

`Free f`での実装は以下です。

```haskell:Free_fのBindインスタンス
instance bindFree :: Functor f => Bind (Free f) where
  bind (Pure x) f = f x
  bind (Free x) f = Free (map (flip bind f) x)
```

納得できない人は同様に型を確かめてみてください。

ここまでで`f`がFunctorのとき、`Free f`にMonadを実装できました。

FreeがFunctorからMonadをつくるとは、こういうことになります。



# 直感的な説明

「Monadを実装できたので、Monadです」では納得できないかもしれないので、なぜMonadを実装できたかの直感的な説明をしておきます。

まずMonadの定義について話します。

Functor / Applicative Functor / Monadの定義から、

```haskell:Monadの定義
map :: (a -> b) -> m a -> m b
pure :: a -> m a
bind :: m a -> (a -> m b) -> m b
```

の3つを実装すれば、Monadになることがわかります。
`apply`は必ずしも必要ではありません。

実際、`pure`と`bind`があれば`apply`は実装できます。

```haskell:applyの実装1
apply :: m (a -> b) -> m a -> m b
apply f x = bind f (\f' ->
    bind x (\x' -> pure (f' x'))
  )
```

do記法を使うと以下のように書けます。
do記法は`bind`のシンタックスシュガーです。

```haskell:applyの実装2
apply f x = do
  f' <- f
  x' <- x
  pure (f' x')
```

閑話休題。

実は、Monadには別の定義もあります。

```haskell:Monadの別定義
map :: (a -> b) -> m a -> m b
pure :: a- > m a
join :: m (m a) -> m a
```

`bind`の代わりに`join`という関数を使います。

この定義が`bind`を使ったものと同じかどうかは、`bind`を実装してみればわかります。

```haskell
bind :: m a -> (a -> m b) -> m b
bind x f = join (map f x)
```

[List as Monad](#list-as-monad)で見たように、`concat :: List (List a) -> List a`はListでの`join`になります。

ここで、`Free`の定義をもう一度見てみます。

```haskell:Freeの定義
data Free f a
  = Pure a
  | Free (f (Free f a))
```

値コンストラクタの型は以下のようになります。

```haskell:Freeの値コンストラクタの型
Pure :: a -> Free f a
Free :: f (Free f a) -> Free f a
```

先ほどのMonadの別定義をもう一度見てみます。

```haskell:Monadの別定義
map :: (a -> b) -> m a -> m b
pure :: a -> m a
join :: m (m a) -> m b
```

すると、`Pure`が`pure`に、`Free`が`join`に対応していることがわかります。

FunctorやMonadを実装する際には、そのデータ型の値コンストラクタを使えるのでした。
つまり、Freeはその**値コンストラクタの形により、Monadを実装することができる**のです。

あとMonadを実装するのに足りないのは`map`だけです。
ここで、**`f`の`map`があると、`Free f`の`map`も実装できた**ことを思い出します。
これが`Free f`の**`f`がFunctorでなければならない理由**となります。

Freeの定義のあの不思議な形には、実はこういった理由があったわけです。



# 余談２：Functor則 / Monad則

Functorの定義は

```haskell:Functorの定義
class Functor f where
  map :: forall a b. (a -> b) -> f a -> f b
```

でした。

しかし、この型クラスを実装するだけでは、本当の意味でのFunctorにはなりません。

本当の意味、とはどういうことでしょうか。

そもそも、Functorは圏論において数学的に定義されたものです。
それをPureScriptの型システム上で表現したものがFunctor型クラスです。

ただし、FunctorにはFunctor則とよばれる、以下の条件があります。

- 恒等射(`identity`)の保存: `map identity = identity`
- (関数)合成の保存: map (f <<< g) = map f <<< map g

`f <<< g`は関数合成`\x -> f (g x)`です。
これらの条件を満たして初めて、本当の意味でFunctorになります。

PursuitにはFunctor則が書いてあります。Pursuit優秀すごい。
[Data.Functor - purescript-prelude - Pursuit](https://pursuit.purescript.org/packages/purescript-prelude/4.1.1/docs/Data.Functor#t:Functor)

PureScriptの型システムにはそこまでの表現力はないので、`map identity = identity`のような条件は保証できません。
よって、FunctorではないFunctor、MonadではないMonadなどが実装できてしまいます。

つまり、コンパイラでは保証できないので、実装を行う人間が保証するしかないということです。[^7]

[^7]: C言語で「お前は配列！」と言いながらポインタを扱うのに似ていますね (暴言)。

同様に、MonadにもMonad則があります。
[Control.Monad - purescript-prelude - Pursuit](https://pursuit.purescript.org/packages/purescript-prelude/4.1.1/docs/Control.Monad#t:Monad)

FunctorやMonadを実装する際には注意する必要があります。