Freeモナドのしくみ

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

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

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の基本と用語の説明

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

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

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

purescript/documentation: Documentation for the PureScript language, compiler, and tools.

Pursuit

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

データ型の定義

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

data構文

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

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

データ型の定義の例

data List a
  = Nil
  | Cons a (List a)

値コンストラクタ

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

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

値コンストラクタの型

-- 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の式です。
また、これ以上評価できない式を値とよびます。²

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

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

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

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

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

パターンマッチの例

case xs of
  Nil -> ...
  Cons x xs -> ...

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

型コンストラクタ

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

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

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

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

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

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

値と型、型とカインドの対応

<値> :: <型>
<型> :: <カインド>

値と型、型とかインドの例

-- <型 or 高カインド型 (型コンストラクタ)> :: <カインド>
List :: Type -> Type
List Int :: Type

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

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

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

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

値コンストラクタと型コンストラクタがややこしい例

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は型です。
ややこしい……。

型クラスの定義と実装

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

定義

class構文1

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

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

class構文1の例

class Functor f where
  map :: forall a b. (a -> b) -> f a -> f b

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

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

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

class構文2

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

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

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

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である」と読めます。

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

関数の型定義の方の=>は、後ほど関数の定義で説明します。

実装

instance構文1

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

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

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のインスタンスを実装する」と読めます。³
これを少し雑に「ListにFunctorを実装する」と言っています。

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

instance構文2

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

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

instance構文2の例

instance eqList :: Eq a => Eq (List a) where
  eq = eq1

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

Data.Eq - purescript-prelude - Pursuit

関数の定義

関数の定義1

<関数名> :: forall <型変数1> <型変数2> ... . <型>
<関数名> <引数名1> <引数名2> ... = <実装>

関数定義1の例

identity :: forall a. a -> a
identity x = x

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

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

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

関数定義2

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

例

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」と読み替えることができるためです。

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

例

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

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

関数定義にもwhereがあります。⁵

例

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の定義は以下とします。

Listの定義

data List a
  = Nil
  | Cons a (List a)

List as Functor

Functorの定義は以下です。

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での実装は以下です。

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の定義は以下です。

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での実装は以下です。

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と違い簡単に思いつきそうにはありません。

というわけで、型パズル⁶の時間です。
型を見ることで、applyを実装する過程を見ていきます。

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

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

です。

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

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

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とします。

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を組み立てます。

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を実装します。

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の定義は以下です。

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での実装は以下です。

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の実装を確かめてみます。

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を実装します。

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の定義は以下のような形をしています。

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の定義は以下です。

Functorの定義

class Functor f where
  map :: forall a b. (a -> b) -> f a -> f b

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

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のとき

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であることがわかります。

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のとき

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)であることがわかります。

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の定義は以下です。

Applyの定義

class (Functor m) => Apply m where
  apply :: forall a b. m (a -> b) -> m a -> m b

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

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を実装します。

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の定義は以下です。

Bindの定義

class (Apply m) => Bind m where
  bind :: forall a b. m a -> (a -> m b) -> m b

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

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の定義から、

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は実装できます。

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のシンタックスシュガーです。

applyの実装2

apply f x = do
  f' <- f
  x' <- x
  pure (f' x')

閑話休題。

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

Monadの別定義

map :: (a -> b) -> m a -> m b
pure :: a- > m a
join :: m (m a) -> m a

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

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

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

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

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

Freeの定義

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

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

Freeの値コンストラクタの型

Pure :: a -> Free f a
Free :: f (Free f a) -> Free f a

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

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の定義は

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

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

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

同様に、MonadにもMonad則があります。
Control.Monad - purescript-prelude - Pursuit

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

---

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

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

3. これも用語が正確に合っているのか自信がありません。 ↩

4. 余談１：値コンストラクタと関数の違いで説明しています。 ↩

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

6. 本当は型を合わせるだけでは十分でないのですが、今回は考えないことにします。余談２：Functor則 / Monad則で説明しています。 ↩

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