Haskell
AOP
tree
Monad
F-Algebra
HaskellDay 25

二分木をモナドにする

$\require{AMScd}$

クリスマスといえば

メリークリスマス!1
クリスマスツリー飾りましたか?
写真は3年目になる我が家のクリスマスツリーです.
家族でわいわい飾り付けました.2

クリスマスといえばやっぱりツリーですよね.
というわけで今日はクリスマスですし,やや強引ですがツリーを題材にして記事を書いてみます.

お題: do { x <- xs; y <- ys; return (x, y) } :: Tree a

リストがモナドなことはご存知でしょう.
リストについてはdo {x <- xs; y <- ys; return (x,y)} :: [a](あるいは[(x, y) | x <- xs, y <- ys])のようにリストxsとysとから直積を生成できますね.

では二分木がモナドになったとして同様のことをするとどんな結果が返ってくるでしょうか?
つまり話題にしようとしているのはdo {x <- xs; y <- ys; return (x,y)} :: Tree aの返り値です.

本記事ではこれをひとまずのゴールに定めてみたいと思います.

たいていの始型(Initial Type)はモナドを生ずる

のっけからツリーとは関係ないですが,たいていの始型はモナドを生じる3らしいです.
イキナリなんのこっちゃ?ってところでしょうからいくつか用語を確認します.

準備

まずはHaskellのデータ型宣言から始めましょう.

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

リストです.4
Haskellにおけるデータ型宣言というのは型とともにその値の集合を定義しています.
特にリストは多相型で,$a$型でパラメータ化されていますので,いわば関数のようなものとみることができます.
つまり$a$型から${\sf List}\,a$型への関数のように思うことができそうです.
そこでこの関数を${\sf F}_a(B) = 1 + a\times{B}$と書くことにしましょう.
しましょうって言っちゃってますけど,上のデータ型宣言と対応しているのでその辺りを確認しておいてください.
Nilが固定値で1になっています.
$+$記号はHaskellでは縦棒(|)にあたっていますね.
$\times$記号の方はConsがそうですが,Haskellではデータ構成子を示す必要があるのでこうなっていますけど,本質的にはタプルだと思ってみてください.
関数のようなものと言っていますがご存知関手です.
型$a$をとって別の型${\sf F}(a)$に写しているだけですね.

パラメータ型$a$もちゃんと引数として与えるように一般化すると${\sf F}(A,B) = 1 + A\times{B}$となります.
この関数に$A$と$B$のふたつの型を渡して新しい${\sf F}(A,B)$型が作れるわけです.
その作り方は右辺のように$1 + A\times{B}$という多項式で表現されています.5
これらの引数それぞれについて${\sf F}$が関手としてふるまうなら${\sf F}$を双関手(Bifunctor)と呼びます.

同様に二分木です.

Leafy.hs
data Leafy a = Tip a
             | Bin (Leafy a) (Leafy a)

この場合には,${\sf F}(A,B) = A + B\times{B}$という関数がこの構造を表現しています.
これもリストと同じように型宣言とこの多項式が対応していることを見ておいてください.

さて,次にこの${\sf F}(A,B)$の$A$と$B$との関係に着目して${\sf T}(A) = {\sf F}(A, {\sf T}(A))$となるような${\sf T}$なる関数を考えるとしましょう.
おっとこの辺でもうなんだか混乱しちゃって分からない??
じゃあ具体的にリストの場合や二分木の場合に何に対応しているかを確かめるとしましょう.
リストなら${\sf T}(A) = {\sf List}\,A = {\sf F}(A, {\sf T}(A)) = 1 + A\times{{\sf T}(A)} = 1 + A\times{{\sf List}\,A}$だから${\sf T}$ってのは${\sf List}$っていう型構成子にあたるかな.
一応二分木の方も.
${\sf T}(A) = {\sf Leafy}\,A = {\sf F}(A, {\sf T}(A)) = A + {\sf T}(A)\times{{\sf T}(A)} = A + {\sf Leafy}\,A\times{{\sf Leafy}\,A}$なので${\sf Leafy}$ですからやっぱり型構成子じゃないかなと分かります.

ただ型構成子というと単に型から新たな型へ写すことしか念頭にないかもしれませんけど,実際にここで${\sf T}$に求められるのは型から型への写像としての役割だけではなく,もとの型の間にある射も相互の関係構造をぶちこわすことなく写すことが期待されています.
この${\sf T}$のことを型関手(Type Functor)と呼ぶようですが,まぁぶっちゃけてしまえばfmapのことです.

データ型の構造を決めている${\sf F}$と${\sf T}$とははっきりと区別すべきものなので注意してください.

あるデータ型宣言があったときにデータ構成子のあつまり,例えばリストなら[Nil,Cons]のことだし二分木なら[Tip,Bin]のことなのですが,こいつはよく$\alpha$と書かれたりします.
[f,g]というのはfかまたはgという二つの関数のどちらかをあらわしていて,二分木の場合だと$A + B\times{B}$の最初の項$A$が来たらTipを,$B\times{B}$が来たらBinを適用するような関数を表現しています.
おっとこれは間違い.
正しくは[Tip, uncurry Bin]ですね.
このように多項式関手で書いていると実際にはuncurry Binにしたくなることが多くなるので,通常はラッパー関数を用意します.

Leafy.hs
tip = Tip
bin = uncurry Bin

そうすると$\alpha$は[tip,bin]などと書けるようになってインターフェースがうまくかみ合います.
まぁ実際にはどっちでやっても実装できるんですがcatamorphismにしたときにいずれにせよcurry/uncurryはごにょごにょしないといけないのでどちらに寄せるかは好みでしょうか...
ともあれ,この流儀でやる場合には以下のユーティリティも一緒に添えておきます.

Leafy.hs
pair (f, g) x = (f x, g x)
cross (f, g) (x, y) = (f x, g y)

これらはそれぞれControl.Arrowなら(&&&)と(***)に相当します.
これも個人的には定義するのを好みます.6
同様にリストであればNilかあるいはConsのどちらかで構成できるので[nil,cons]が$\alpha$というわけです.

Leafy.hs
nil = Nil
cons = uncurry Cons

nilをこのようにNilとあわせちゃうかNil ()と引数を取るようにするかはまたこれも微妙なのですが,あんまりなんでもかんでも横道にそれまくると終わらないので今回はスルーで.7
ちなみにこのような$\alpha$を始代数と呼んだりします.

型関手${\sf T}$と$\alpha$とはもうワンセットで考えていいんですけど,一応合わせて${\sf (\alpha, T)}$を始型(Initial Type)と呼びます.
具体例で言えばリストなら$\alpha$ってのは[nil,cons]ですから関手${\sf F}$の始型というのはその関手であらわされる型のデータ構成子[nil,cons]とその型への写像mapとをワンセットにしたものを始型と呼んでるんだなーくらいな感じで.

お前さっきから呼びます呼びますばっかだなって嫌気がさしてきた頃あいだと思いますが,一応今回はこれでおよそ用語は出そろいました.

さらにあとで話をややこしくが見えやすくするためにもういっちょ二分木に登場してもらいます.

Traditioanl.hs
data Tree a = Empty
            | Node a (Tree a) (Tree a)

この二分木は${\sf F}(A,B) = 1 + A\times{B\times{B}}$という多項式で表現できますね.
ちなみにこちらの二分木をTraditional Binary Treeと呼んで,最初のをLeafy Treeと呼んでいるコンテキストを見かけたことがあるのでここでもその呼び方を流用させていただくこととします.8

さて二分木らしきものがふたつ登場しました.
このどちらか一方は簡単にモナドにできますがもう一方に良いモナド(good monad)はありません.
どっちがモナドにできるか分かるかな?

たいていの始型をモナドにしよう

じゃあ早速やってみよう.
といいたいところですが,もうちょっと辛抱してください.9
単項関手${\sf G}$と${\sf H}$があるとして,${\sf L}(A) = {\sf F}({\sf G}(A), {\sf H}(A))$となるように関手${\sf L}$を定義します.
さて,もし$\phi :: {\sf L\rightarrow{H}}$なる$\phi$があったら$(|\phi|) :: {\sf TG\rightarrow{H}}$となります.
証明は省きますが可換図式だけ示しておきます.
えーっと,ここで$(|$と$|)$とで囲っているのはバナナ括弧のつもりです.念のため.

\begin{CD}
{\sf F}({\sf G}A, {\sf TG}A) @>\alpha>> {\sf TG}A \\
@V{\sf F}(id,(|\phi|))VV @V(|\phi|)VV \\
{\sf F}({\sf G}A, {\sf H}A)\equiv{{\sf L}A} @>\phi>> {\sf H}A
\end{CD}

いきなり記号は増えるわ構造はややこしくなるわで何がしたいんだか分からない人のために少し補足しておきます.
ひとつにはこれ${\sf F}(A,{\sf T}(A))$をより一般化した形にしてますね.
逆に言うと${\sf F}({\sf G}(A), {\sf H}(A))$の特別な場合として${\sf G}$を恒等関手に,${\sf H}$を型関手${\sf T}$にとると${\sf F}(A,{\sf T}(A))$になるわけです.
つまり対象とするデータ型の構造を規定する${\sf F}$を一般化しようとしているわけです.

もうひとつには,上の可換図式のとおり$\phi : {\sf F}({\sf G}A, {\sf H}A)\rightarrow{\sf H}A$にとっての始代数は$\alpha : {\sf F}({\sf G}A, {\sf TG}A)\rightarrow{\sf TG}A$になりますが,ここで${\sf G}$を恒等関手において,さらに$A$を${\sf T}A$に,その上で${\sf H}$を${\sf T}$にとると次のような図式になります.

\begin{CD}
{\sf F}({\sf T}A, {\sf TT}A) @>\alpha>> {\sf TT}A \\
@V{\sf F}(id,(|\phi|))VV @V(|\phi|)VV \\
{\sf F}({\sf T}A, {\sf T}A) @>\phi>> {\sf T}A
\end{CD}

こうすれば$(|\phi|) : {\sf TT}A\rightarrow{\sf T}A$として$\mu$つまりHaskellでいうところのjoinが手に入りそうだぞってことが容易に分かるというわけですね.
言ってしまえば,このような構造になっている${\sf F}$双関手がベースになる型では${\sf F}({\sf T}A, {\sf T}A)\rightarrow{\sf T}A$な関数を作ってしまえばそのcatamorphismとしてjoinが書けるってことです.10
さてここで${\sf F}(A,B) = A + {\sf G}B$あるいは射の上であらわせば${\sf F}(f, g) = f + {\sf G}g$なる双関手を考えます.
また$(\alpha, {\sf T})$を${\sf F}$の始型としましょう.
そうするとなんと$\phi = \alpha\cdot{inl}$と$\psi = (|id,\alpha\cdot{inr}|)$と定義することで$({\sf T},\phi,\psi)$がモナドになることが証明できます.
いわゆるモナド則をぜーんぶ証明すればよいのですが,ここでは省略します.

これでようやく準備が整いました.

二分木(Leafy)をモナドに

さてさてそれでは引き続き${\sf F}(A,B) = A + {\sf G}(B)$の場合を考えましょう.
これは上で説明した${\sf L}$における${\sf F}$を単なる直和と捉えて,${\sf G}$を恒等関手,${\sf H}$を${\sf G}$と読み直しただけのものです.

Leafyな二分木は${\sf G}(B) = B\times{B}$となるような${\sf G}$を取った場合だとみることができます.
つまり${\sf F}_A(B) = A + {\sf G}(B) = A + B\times{B}$なる関手${\sf F}$の不動点がLeafyな二分木です.

この場合,${\sf T}$という型関手はというと$mapt\,f = (|\alpha\cdot{{\sf F}(f,id)}|) = (|[tip,bin]\cdot{(f+id\times{id})}|) = (|tip\cdot{f},bin\cdot{(id\times{id})}|)$という風に代数的に解けます.
また$\phi = \alpha\cdot{inl} = [tip,bin]\cdot{inl} = tip$であることと$\psi = (|id, \alpha\cdot{inr}|) = (|id, [tip,bin]\cdot{inr}|) = (|id, bin|)$が代数的に解けちゃいますので,そのままHaskellに落とし込めば以下のようなコードになります.

Leafy.hs
mapt f = foldt (tip.f, bin.cross(id,id))
eta = tip
mu = foldt (id,bin)

ここで$foldt$はこのLeafyな二分木のcatamorphismです.

\begin{CD}
A + {\sf T}A\times{{\sf T}A} @>\alpha\equiv{[tip,bin]}>> {\sf T}A \\
@V{id+u\times{u}}VV @V{(|f,g|)\equiv{u}}VV \\
A + X\times{X} @>{[f,g]}>> X
\end{CD}

これもHaskellに写し取れば以下のようになります.

Leafy.hs
foldt (f, g) (Tip x) = f x
foldt (f, g) (Bin l r) = g (foldt (f, g) l, foldt (f, g) r)

{- ekmett like
foldt (f, g) = u
  where
    u (Tip x) = f x
    u (Bin l r) = g (u l, u r)
-}

コメントでEkmett流って書いてますが別にEkmettさんがこのコードを実際に書いていたというわけではなくEkmettさんのライブラリを見ているとおよそ彼が書くとこんな感じで書くかなというものですので彼に問い合わせないようにお願いします.1112
お約束に従って$({\sf T},\phi,\psi)$を取ったので,モナドになることが保証されているわけですからインスタンスにしてみます.

Leafy.hs
instance Monad Leafy where
  return = eta
  m >>= f = mu (fmap f m)

こんな感じです.
もちろん,これを書くためにはFunctorとApplicativeのインスタンスにする必要があるので,以下のようにします.

Leafy.hs
instance Functor Leafy where
  fmap = mapt
  -- a <$ (Tip _) = tip a
  -- a <$ (Bin l r) = bin (a <$ l, a <$ r)

instance Applicative Leafy where
  pure = eta
  Tip f <*> x = fmap f x
  Bin l r <*> x = bin (l <*> x, r <*> x)

ともあれ二分木がモナドになったので少し遊んでみます.13
ghci を起動してREPLから.

*Leafy> :{
*Leafy| do
*Leafy| x <- bin (tip 1, tip 2)
*Leafy| y <- bin (tip 'A', tip 'B')
*Leafy| return (x, y)
*Leafy| :}
Bin (Bin (Tip (1,'A')) (Tip (1,'B'))) (Bin (Tip (2,'A')) (Tip (2,'B')))
*Leafy> :{
*Leafy| do
*Leafy| x <- bin (tip 1, bin (tip 2, tip 3))
*Leafy| y <- bin (tip 'A', tip 'B')
*Leafy| return (x,y)
*Leafy| :}
Bin (Bin (Tip (1,'A')) (Tip (1,'B'))) (Bin (Bin (Tip (2,'A')) (Tip (2,'B'))) (Bin (Tip (3,'A')) (Tip (3,'B'))))
*Leafy> :{
*Leafy| do
*Leafy| x <- bin (tip 1, bin (tip 2, tip 3))
*Leafy| y <- bin (bin (tip 'A', tip 'B'), tip 'C')
*Leafy| return (x, y)
*Leafy| :}
Bin (Bin (Bin (Tip (1,'A')) (Tip (1,'B'))) (Tip (1,'C'))) (Bin (Bin (Bin (Tip (2,'A')) (Tip (2,'B'))) (Tip (2,'C'))) (Bin (Bin (Tip (3,'A')) (Tip (3,'B'))) (Tip (3,'C'))))
*Leafy> bin (tip 1,tip 2) >>= \x -> bin (tip 'A',tip 'B') >>= \y -> return (x, y)
Bin (Bin (Tip (1,'A')) (Tip (1,'B'))) (Bin (Tip (2,'A')) (Tip (2,'B')))
*Leafy> bin (tip 1, bin (tip 2, tip 3)) >>= \x -> bin (tip 'A', tip 'B') >>= \y -> return (x, y)
Bin (Bin (Tip (1,'A')) (Tip (1,'B'))) (Bin (Bin (Tip (2,'A')) (Tip (2,'B'))) (Bin (Tip (3,'A')) (Tip (3,'B'))))
*Leafy> bin (tip 1, bin (tip 2, tip 3)) >>= \x -> bin (bin (tip 'A', tip 'B'), tip 'C') >>= \y -> return (x, y)
Bin (Bin (Bin (Tip (1,'A')) (Tip (1,'B'))) (Tip (1,'C'))) (Bin (Bin (Bin (Tip (2,'A')) (Tip (2,'B'))) (Tip (2,'C'))) (Bin (Bin (Tip (3,'A')) (Tip (3,'B'))) (Tip (3,'C'))))
*Leafy> let t = bin (tip (bin (tip (bin (tip 1, tip 2)), tip (bin (tip 3, tip 4)))), tip (bin (tip (bin (tip 5, tip 6)), tip (bin (tip 7, tip 8)))))
*Leafy> :t t
t :: Num a => Leafy (Leafy (Leafy a))
*Leafy> mu t
Bin (Bin (Tip (Bin (Tip 1) (Tip 2))) (Tip (Bin (Tip 3) (Tip 4)))) (Bin (Tip (Bin (Tip 5) (Tip 6))) (Tip (Bin (Tip 7) (Tip 8))))
*Leafy> fmap mu t
Bin (Tip (Bin (Bin (Tip 1) (Tip 2)) (Bin (Tip 3) (Tip 4)))) (Tip (Bin (Bin (Tip 5) (Tip 6)) (Bin (Tip 7) (Tip 8))))
*Leafy> mu (mu t) == mu (fmap mu t)
True
*Leafy>

というわけで本記事の一応の到達点にやってきました.
do { x <- xs; y <- ys; return (x, y) } :: Tree aの返り値はこうなるんですね.
お疲れ様でした.

さて,ここで見ておきたいのは$\psi$つまり$\mu$ですが,これはリストモナドならconcatのことでした.
$\mu$は二分木においては葉のところにさらに次の階層の二分木が入れ子になっているときに,上位階層の枝に接ぎ木するようなものだとみることができます.
$\mu$をリストモナド上だけで理解しているとconcatつまり同じレベルに並んだリストを横に連結するんだ,というリストにしか通用しない理解で終わってしまいがちです.
二分木における$\mu$を見ると,あれは横に連結しているというよりはむしろ,リストの要素として入れ子になっているリストを上位側のリストに接ぎ木(埋め込み)した結果として要素がべろべろっと展開されたようなもんだと解釈できます.14
同様にリストだとdo { x <- xs; y <- ys; return (x, y) } :: [a]についてよく「xsが先に繰り返されるかysが先に繰り返されるかどっちだっけ?」みたいな話をしますが,繰り返すというよりはどっちが基本構造を提供しているか?という方が良さそうに思います.
少なくともこの実装の場合には,xsが基本構造を提供していて,その葉の部分にysが展開されて,それが$\mu$で接ぎ木されているというのがリストにも二分木にも通用する理解じゃないかと思います.

はい.
ともあれLeafyな二分木の方はgoodなモナドになりました.
ということは次のTraditionalな方はダウトってことですね.

二分木(Traditional)をモナドに

前のセクションの帰結としてこちらはすでにダメだと分かっているんですが,なぜダメなのかを見ておくのは有用なので検討だけはしておきます.
あらためて型の定義を再掲しておきます.

Traditional.hs
data Tree a = Empty
            | Node a (Tree a) (Tree a)

こいつのデータ構造は${\sf F}(A,B) = 1 + A\times{B}\times{B}$であらわされるのでした.
Leafyな二分木のときと同じように進めるとします.

まずcatamorphismは良いでしょう.

\begin{CD}
1 + A\times{{\sf T}A\times{{\sf T}A}} @>\alpha\equiv{[empty,node]}>> {\sf T}A \\
@V{id_1+id_A\times{u}\times{u}}VV @V{(|c,h|)\equiv{u}}VV \\
1 + A\times{X\times{X}} @>{[c,h]}>> X
\end{CD}

なのでそのままHaskellのコードに落とせば

Tree.hs
foldtt (c, h) Empty = c
foldtt (c, h) (Node x l r) = h (x, foldtt (c, h) l, foldtt (c, h) r)

{- ekmett like
foldtt (c, h) = u
  where
    u Empty = c
    u (Node x l r) = h (x, u l, u r)
-}

とこんな風に書けばよいはずです.
すると$maptt\,f = (|\alpha\cdot{{\sf F}(f, id)}|) = (|[empty, node]\cdot{(1 + f\times{id}\times{id})}|) = (|empty, node\cdot{(f\times{id}\times{id})}|)$と代数的に解けますね.
これも同様にHaskellに落とし込めます.

Tree.hs
maptt f = foldtt (empty, node . cross3 (f, id, id))
  where
    cross3 (f, g, h) (x, y, z) = (f x, g y, h z)

ってところでしょうか.

では$\phi$と$\psi$はどうか?
そもそも${\sf F}_A = A + {\sf G}B$という形ですらなく,${\sf F}_A = 1 + {\sf G}(A,B)$という形をしているのでとりあえずLeafyの時に使った$\phi$や$\psi$の式は流用できません.
もちろんだからといって可能性がないわけではなく,この形の場合にはどうなのかを考えれば良いわけです.

では自力で考えてみましょう.
$\phi$というのは次の図式のような射であってほしいわけです.

\begin{CD}
A @>?>> 1 + A\times{{\sf T}A}\times{{\sf T}A}
\end{CD}

いくつか考えられます.15
おそらくは次のふたつのうちのどちらかが妥当なんじゃないか?という感じでしょうか.

Tree.hs
eta1 x = empty

eta2 x = node (x, empty, empty)

これらは上の図式でいうところの1側の構成子をとるか,それとも$A\times{{\sf T}A}\times{{\sf T}A}$をとるかの2択を考えているだけです.
eta1はいかにもダメそうです.なんせ引数がなくなっちゃってますからね.
eta2は有望そうですね.

では$\psi$の方を検討してみます.

\begin{CD}
1 + {\sf T}A\times{{\sf TT}A\times{{\sf TT}A}} @>\alpha\equiv{[empty,node]}>> {\sf TT}A \\
@VVV @V(|k|)VV \\
1 + {\sf T}A\times{{\sf T}A\times{{\sf T}A}} @>k>> {\sf T}A
\end{CD}

とりあえずkが自然な形で実装できればそのcatamorphismで$\mu$が得られるわけです.
もちろんモナド則を満たす必要がありますが,値に依存しないような自然な形で上から接ぎ木しても下から接ぎ木してもかまわないように考えればよいのでそう難しい話ではないです.
でも実際のところ$1+{\sf T}A\times{{\sf T}A}\times{{\sf T}A}\rightarrow{{\sf T}A}$な関数を実装できるでしょうか?

なかなかの難問です.
結局${\sf T}A\times{{\sf T}A}\times{{\sf T}A}$という3つの二分木をひとつの二分木にまとめ上げないといけないのにその中から特定の$A$を祭り上げる必要があります.
そのくせどの二分木もEmptyを任意に含みうるのでその時点で場合分けが発生し,モナド則を満たすような接ぎ木のルールになるか?というとかなり厳しいでしょう.
それ以前に全部がEmptyだったらどうやっても木を構成できませんし.

逆に$\eta$として最初にダメでしょって言ってたeta1を使うことにして$\mu$として$k = const\,empty$としてしまえばなんでもかんでもEmptyになってモナド則は満たしそうです.
ですがこれではgoodなモナドとは言えないでしょう.
なんせすべてがEmptyにつぶれてしまうわけですから意味がないですし,型の構造に固定値1を含む型であればなんでも同じことになってしまいます.
つまりそのようなモナドはTree型である必要性がなくなってしまいます.

ちょっと考察

モナドにする上で型の構成が$A + {\sf G}B$という関手になっていることは入れ子になった構造をモナド則を満たすように接ぎ木するうえで非常に都合が良いことが分かります.
そう考えるとむしろリストが$1 + {\sf G}_A(B)$という形になっているのにモナドになるのはとても興味深いです.
この観点からすれば,リストの場合には要素の並びを左から右へ一意に決定できるので,ある意味たまたまうまくいく実装が見つけられたとさえ言えそうです.

Freeモナド

もう少し${\sf F}(A,B) = A + {\sf G}(B)$をじっくり鑑賞してみたいと思います.

記事の途中からは,この形式の双関手${\sf F}$が型の構造を決めているという極めて特殊な状況だけを考えてきたわけですが,この場合においては任意の単項関手${\sf G}$に対して${\sf F}_{A}$は自動的にモナドにできる.
というのがこの話題のキモでした.

ここではこの構造のもっとも基本的な部分だけを観察するために${\sf G}$として恒等関手を取ってみます.
つまり${\sf F}_{A}(B) = A + B$です.
あるいは${\sf F}(A,{\sf T}A) = A + {\sf T}A$と書いても同じことですが,型関手があらわになることでより輪郭がはっきりするでしょうか.

Free.hs
data Free a = Pure a | Roll (Free a)

pure' = Pure
roll  = Roll

これはもちろんモナドにできます.
型関手(freeMap)は$(|\alpha\cdot{{\sf F}(f,id)}|) = (|[pure',roll]\cdot{(f + id)}|) = (|pure'\cdot{f}, roll|)$で代数的に求めています.
$\eta$は$\alpha\cdot{inl} = [pure',roll]\cdot{inl} = pure'$により,また$\mu$は$(|id,\alpha\cdot{inr}|) = (|id,[pure',roll]\cdot{inr}|) = (|id,roll|)$によりそれぞれ代数的に求めることができます.

Free.hs
cata :: (a -> b, b -> b) -> Free a -> b
cata (f, g) (Pure x) = f x
cata (f, g) (Roll x) = g (cata (f, g) x)

freeMap :: (a -> b) -> Free a -> Free b
freeMap f = cata (pure' . f, roll)

instance Functor Free where
    fmap = freeMap

instance Applicative Free where
    pure = pure'
    (<*>) = cata (fmap, (roll.))

eta :: a -> Free a
eta = pure'
mu :: Free (Free a) -> Free a
mu = cata (id, roll)

instance Monad Free where
    return = eta
    m >>= f = mu (fmap f m)

ご存知の方にはなんなんですが,今さらながらFreeモナドです.16
Freeモナドは(誤解をおそれずに言えば)${\sf G}$とは無関係にモナドになります.
パラメータ化してみると以下のようになります.

Free.hs
data Free g a = Pure a | Roll (g (Free g a))

このFreeは上のFreeとは違います.
Free gが上で言うところのFreeに相当しますのでご注意ください.
まぁFreeFとでも書いた方がいいくらいかもしれません.

念の為おことわりしておくと,任意の関手${\sf G}$がモナドにできるのではありません.
単項関手${\sf G}$があれば,${\sf F}(A,{\sf T}A) = A + {\sf G}({\sf T}A)$な関手${\sf F}$に埋め込めるというだけです.
関手${\sf G}$をタダでモナドにできるわけでもなんでもなく,Freeは元からモナドにできる構造で,単項関手${\sf G}$の構造は正直なところ関係ないです.

自作のデータ型をモナドにするのはモナド則を満たすようにしなければならないという点で非常にハードルが高いのですが,一方で関手にするのは簡単です.1718
Freeモナドは言わばモナドになることがあらかじめ分かっている再帰的データ構造の汎用パターンを用意してくれているという点でフレームワークのようなものです.

たとえばこの記事であつかったLeafyな二分木のモナドを作りたいと思ったとしましょう.
Freeモナドを積極的に使うつもりならあなたが定義すべきデータ型は,

Example.hs
data G a = G a a

になります.
あなたが定義するのは作りたいと思っていたLeafyな二分木そのものではないです.
悪く言えば作りたいと思っていた構造とはややズレたデータ型を宣言させられるハメになります.
つまりあなたが欲しかったデータ構造がFreeになるとして,そこから逆算して${\sf G}$を宣言することになります.
あるいはLeafyなツリーを定義しておきながらFreeに埋めて「Free便利~♪」とかやるのはやや恥ずかしいので,なるたけ避けましょうというだけのお話です.

この記事で紹介したのは,${\sf F}$の構造についてかなり限定されてはいますがそれでも相当一般的にモナドにできる再帰的データ型の構成法のひとつです.19
この記事をここまで読まれた方であれば,もともとモナドにしたいと思っていたものとはちょっとズレた${\sf G}$を作ってからFreeの力を借りてモナドを手に入れるのではなく,直接モナドになるようにデータを定義できるはずです.
もちろん欲しいデータ構造が本当にモナドにできるようなものならですけど.

というわけで「たいていの始型はモナドを生じる」ってのはなーんだそんなことかーって分かっていただければ成功なんだけど,どうだったでしょうか.

さいごに

この記事はAOP3の一連の練習問題にインスパイアされています.
${\sf F}(f,g) = f + {\sf G}g$という形の双関手に対し,$(\alpha, {\sf T})$をその始型としたとき,$\eta$と$\mu$とを本記事で紹介した式に当てはめれば$({\sf T},\eta,\mu)$がモナドになることを証明し,${\sf G}(g) = g\times{g}$とした時にそれが何を意味するかを問うものです.
Freeモナドという言葉こそでてきませんが,練習問題はまさにFreeモナドがモナド則を満たすような$\eta$と$\mu$の構成(解)を示していました.

証明に関心のあるかたはやってみると良いと思いますが,われわれ一般のプログラマにとっては基本それでモナドにできるということさえ把握できていれば良いだろうと思います.20
個人的にはFreeモナドの関手構成は制限されすぎていると感じており,途中でも書きましたが標準的なリストでさえ当てはまらないことが不満です.
もっと一般化された,あるいはどういった構成の関手構造ならばモナドにできる$\eta$や$\mu$が代数的に計算可能なのかにも興味がありますが,他にも優先度の高い関心事も多々あるためあまり真剣に時間を取って調べてはいません.21
もしご存知のかたがいらっしゃいましたら是非ご教授いただきたいと思います.

個人的には${\sf G}$という関手を手にしつつ,それ自体をモナドにするのではなくFree ${\sf G}$なるモナドを使うという場面は正直あまりよく分かりません.
ネタとして簡単にモナドが手に入るというのはキャッチーだとは思うものの,ながく放置していました.
昨年のアドカレの頃に練習問題を通してFreeの存在に気づいてしまったのでネタにしようかと思ったものの,やれてなかったので今年は記事にできて満足です.

より意欲のある方々向けにお正月のヒマツブシ用に宿題を出しておきましょう.

  1. Haskellの標準ライブラリ(conatinersパッケージのData.Treeモジュール)にあるツリーはローズツリーです.この型を表す関手を書いてみてください.(木と森の相互再帰的定義になっています)
  2. 1の式から森の関手を消去して木が実質二分木であることを確認してください.LeafyかTraditionalかどっちと同じでしょうか?
  3. 木と森のcatamorphismを同時に定義してみてください.
  4. 木と森の型関手を同時に定義してみてください.
  5. 木のモナドとなる$\eta$と$\mu$とを実装してみてください.可能なら森も同様に実装してみてください.(>>=)の形に共通点はあるでしょうか?

なお,回答記事を書く予定はございません.22
それでは,よいお年を.


  1. イエーイ!無宗教デース!! 

  2. 今年もひとつディズニーなオーナメントを追加購入しましたけど最近は娘の工作もつるされてなかなかカオス. 

  3. "Algebra of Programming" R.Bird and De Moor 

  4. いきなりツリーじゃねーし 

  5. この${\sf F}$を使えばじゃんじゃか新しい型を作れちゃうわけですが,上記のHaskellの型宣言は$B = {\sf F}(A,B)$となるようなトクベツな型を宣言しているという体になっています. 

  6. Bird信者なので. 

  7. 興味があったら実装してみればよいです.catamorphismとtype functorあたりを実装すれば違いがわかると思います. 

  8. Ref.) Finger Trees by Edward Kmett 

  9. なんか軽いノリでちょっと待ってねって言っているけどこのセクションが最難関だと思ってる.多分各自で証明に取り組むのが最善かと思います. 

  10. 当然ですが$\mu$がモナド則を満たすような自然な$\phi$を探さないといけないという意味でなんでもいいわけではないです. 

  11. 探せばかなり高確率で書いてそうだけど調べてないです.あと精確に言えば彼のライブラリコードというよりは,説明用のコメント用コードあるいは初期コードといったところでしょうか.いつの日か,細かすぎてわかりにくいモノマネ選手権あたりで出したいネタです. 

  12. ちなみにEkmett流のコードだとidのような自然変換が頻出したときに可換図がないと分からないという現象がよくあります.どれもこれも具体的な型は違っていて,図式中では別の箇所に登場する射だったりするのでポイントワイズにするなり図式を描かないとダマされやすいと思いますがそんなことないですか?別に彼のせいではなくてcatamorphismやらtype functorがそういう構造だからってだけですけどね.その証拠にEkmett流は可換図式をさらにほとんどそのまま書き出した形になっていてキモチ良いです. 

  13. 遊ぶには実際にはderiving Showなどが必要です. 

  14. 細かく見れば[]が吸収されてなくなることと非空リストもheadとtailとはちょっと扱いが異なるんですけど,まぁザツに言えばべろべろっと展開されるとみていいんじゃないかと. 

  15. もちろんLeafyの場合にだって一意に決まったわけではなく$\phi$の型を満たすような射は他にも考えられるのでTraditional Treeに限った問題ではないです. 

  16. 数年前にブログ記事のネタとしてはピークを完全に終えたのでホントにイマサラすぎてごめんなさい. 

  17. deriving Functorでよい.というのは冗談ですが自動的に導出出来るってことはある意味自明だからでもあるのであながち間違ってはないかな. 

  18. とはいえFreeでモナドが作れたと思える精神性があるならすでにハードルは限りなく0になってて自分でモナドになるように型を定義できますよねぇ. 

  19. 限定されているといってもFreeと同等です.つまりFreeは不自由だというシャレです. 

  20. ちなみに証明は難しくはないもののそこそこの前提となる定理やらなんやらが大量に出てくるのでブログでちょろっと書くボリュームではないかなと思います. 

  21. さしずめガロアなら関手構造の対称性に着目するところか? 

  22. 各自苦しめ:-p健闘を祈る.