実用的なFreeモナド(purescript-free)の秘密を探る
序
以前私は「フリーモナドを自分で作ってみよう」という趣旨の記事を投稿したのですが、そのときのフリーモナドの作例は簡単に作って遊べるよう非常にシンプルなものでした。
しかしそれはあくまで作って理解するためのもの。
実際にあちこちで使われている実用に耐えうるフリーモナドとは異なります。
ではそのようなフリーモナドはどのように作られているのでしょうか?
今回は、そんな実用的なフリーモナドの機能がどのように実現されているかを解説したいと思います。
解説に用いるフリーモナドのライブラリはpurescript-freeとします(というかこれ一択?他にいいライブラリはあるのでしょうか?)。
おことわり
- purescript-freeは複雑ゆえ、解説もクソ長いです。ごめんなさい。
- 記事中のpurescript-freeのコードは、実際のライブラリのコードを用いていますが、わかりやすさのため一部の関数に私が型アノテーションを加えていますのでご了承ください。
解説していくぞ
解説に使うサンプルコード
Free
はライブラリなので、Free
の解説にはFree
を使って動かすコードが必要でしょう。
ということでまず、解説に使うためのサンプルコードを載せます。
こちらのコードに対し解説を加えていきたいと思います。
ちなみにこのコードはpurescript-freeに含まれるサンプルコードを利用したものです(ちょっと削った)。
import Prelude
import Effect (Effect)
import Effect.Console (log)
import Control.Monad.Free (Free, foldFree, liftF)
data TeletypeF a = PutStrLn String a | GetLine (String -> a)
type Teletype a = Free TeletypeF a
putStrLn :: String -> Teletype Unit
putStrLn s = liftF (PutStrLn s unit)
getLine :: Teletype String
getLine = liftF (GetLine identity)
teletypeN :: TeletypeF ~> Effect
teletypeN (PutStrLn s a) = const a <$> log s
teletypeN (GetLine k) = pure (k "fake input")
run :: Teletype ~> Effect
run = foldFree teletypeN
echo :: Teletype Unit
echo = do
a <- getLine
putStrLn a
main :: Effect Unit
main = do
run echo
Free
型の定義
サンプルコードを見たところで、Free
の解説に移っていきますよ。
まずは型の定義をみましょう。すべてはそこから始まる。
ということでFree
のコードから、型の定義部分を抜粋してきました。。
data Free f a = Free (FreeView f Val Val) (CatList (ExpF f))
newtype ExpF f = ExpF (Val -> Free f Val)
data FreeView f a b = Return a | Bind (f b) (b -> Free f a)
data Val
シンプルなフリーモナドの定義と比べてみましょうか。
data Free f a
= Pure a
| Free (f (Free f a))
・・・・・・どうです?シンプルな定義と比べてやけに複雑になっていませんか?
型の解説を行う前に、このような複雑な定義になっている理由をお伝えしたいと思います。
なぜならば、この定義の複雑さに付随してFree
のモジュールの関数も複雑になっているため、ここの説明をしておくことが、理解の助けに繋がるからです。
複雑さの理由(ワケ)
なぜこのように複雑になっているかですが、私は大まかに2つの理由があると考えています。
- フリーモナドの生成における
Functor
の制約を無くす - パフォーマンスを上げる
Functor
の制約を無くす
まず「1」ですが、一般的に紹介されているフリーモナドは、食わせる値の型がFunctor
のインスタンスになっている必要があると思います。
以前の記事で作ったフリーモナドを例にとると、モナドにするための各種インスタンスにFunctor
の制約があります。
そしてそれは実装にmap
関数を利用しているためでした。
instance functorFree :: (Functor f) => Functor (Free f) where
map f (Pure a) = Pure (f a)
map f (Free fa) = Free (map f <$> fa)
instance applyFree :: (Functor f) => Apply (Free f) where
apply = ap
instance applicativeFree :: (Functor f) => Applicative (Free f) where
pure = Pure
instance bindFree :: (Functor f) => Bind (Free f) where
bind :: forall a b. Free f a -> (a -> Free f b) -> Free f b
bind (Pure a) fn = fn a
bind (Free f) fn = Free $ (\a -> a >>= fn) <$> f
instance monadFree :: (Functor f) => Monad (Free f)
一方purescript-freeのフリーモナドであるFree
は、Functor
の制約なしにフリーモナドの恩恵にあずかることができます。
Functor
が要らないという意味では、Freerモナドと考えていいかもしれません。
FreerモナドはフリーモナドにCoyoneda
と呼ばれる型を埋め込んだ構造になっていると説明されているのをよく見ます。
(参考:私が昔書いたFreerモナド導出の流れ、および簡単なFreerモナドのコード)
しかしpurescript-freeにはCoyoneda
が存在するものの、Free
の定義では使われておらず、いまの定義で実現しているようです。
パフォーマンスを上げる
次に「2」の「パフォーマンスを上げる」です。
purescript-freeのgithubのREADME.mdには
フリーモナドの実装は、シーケンシャルなデータ構造を使って表現されます。詳細は以下を参照してください
- Reflection without Remorse (Ploeg and Kiselyov 2014)
と書かれています。
そしてそのすぐあとに、左結合のbind
と右結合のbind
におけるパフォーマンスを2バージョンで比較したベンチマークの画像が貼られています。
上記の論文では次のようなことが書かれています(概要や内容から抜粋)。
- モナドは左結合にするとアルゴリズム的にパフォーマンスが低下する。
- その問題に対する解決方法としてCPS(Continuation Passing Style) 継続渡しスタイル がよく知られている。
- ただしCPSが解決できるのは特定の使用パターンのみである。連結の中間の値をobserveしたり、他の連結の部分を用いて連結を構築する必要がある場合、性能はすぐに低下する。
- モナドの結合のような形式は抽象的なシーケンスであり、シーケンスは明示すべきである(一般的な
bind
の実装や、CPSを用いた方法などは暗黙的なシーケンスとなっていると主張されている)。 - シーケンスの表現を明示的にすることで、より適切なシーケンスデータ構造を選択することができ、どのような使用パターンに対しても性能問題を解決することができる。
- 左引数の型が右引数の型に依存する演算子を含む式(
bind
はそうですね)を明示的に表現するためにType aligned sequences
(型整列されたシーケンス)が必要。 - フリーモナドの性能問題も同じアプローチで解決できる。
purescript-freeのFree
では、Type aligned sequences
を構築するデータ構造としてCatenable List
を使っています。
定義を見てみると CatList
というのがいますね。これがCatenable List
です。
data Free f a = Free (FreeView f Val Val) (CatList (ExpF f))
ここまででなぜ定義が複雑化しているかの説明が終わりました。
では予定していた通り、定義の解説に戻りましょう。
Free
型の定義(再)
ここまでの前提を踏まえて再度、Free
の定義を見てみましょう。
data Free f a = Free (FreeView f Val Val) (CatList (ExpF f))
newtype ExpF f = ExpF (Val -> Free f Val)
data FreeView f a b = Return a | Bind (f b) (b -> Free f a)
data Val
まず型構築子Free f a
の部分ですが、型引数a
はデータ構築子の部分に一切登場しません。
つまりPhantom Type
になっています。
FreeView
続いて型構築子FreeView f a b
を見てみましょう。
Bind (f b) (b -> Free f a)
とReturn a
という2つのデータ構築子が存在します。
このBind
は名前から想像がつくかもしれませんが、関数bind
をデータとして表したものといえます。
両者を比較してみると分かりやすいです。
Bind (f b) (b -> Free f a)
-- こちらは関数のbind
bind :: forall a b. m a -> (a -> m b) -> m b
Return
の方は関数pure
をデータとして表したものといえます。
Val
次にFree
のデータ構築子としてFreeView
が使われている部分を見てみましょう。
-- ~~~~~~~~~~~~~~~~~~
data Free f a = Free (FreeView f Val Val) (CatList (ExpF f))
何か変ではありませんか?
FreeView
はFreeView f a b
という型構築子なのに、なぜか型引数にa
やb
が登場せず、Val
などというよくわからんものが使われていますね?
これはPureScriptでは次のように存在量化ができないからです(右辺にforall
が書けない)。
型構築子にb
を登場させずにデータ構築子にb
を登場させることはできないということです(Haskellは言語拡張でできる)。
data Free f a = forall b. Free (FreeView f Val b) (CatList (ExpF f))
こういう場合のアプローチとして私が見かけたことがあるのがpurescript-existsというライブラリを使う方法です。
次のようにExists
という型を使うことでb
の存在を隠蔽できます(使うときはb
が「ある」とすて扱うための関数がある)。
data FreerBindF f a b = FreerBindF (f b) (b -> (Freer f a))
data Freer f a
= Pure a
| Bind (Exists (FreerBindF f a))
Free
の場合は、Exists
ではなく、Val
という空のデータ型を使うことで同じことを実現しています。
データ構築子でVal
を使わず、(FreeView f a b)
のようにすると、上記のように存在量化できないゆえに型構築子の方にもb
を登場させざるを得なくなってしまいます。
が、これであればFreeView
のa
もb
もVal
で隠蔽できます。
ちなみにこのVal
の部分が実際の処理でどう扱われているかは後々説明します。
ExpF
ExpF
はBind
の(b -> Free f a)
と同じ型の関数を持っている型です。
ここでもVal
が使われています。
-- ~~~~ ~~~~
newtype ExpF f = ExpF (Val -> Free f Val)
後述しますが、bind
で繋いでいった関数を保持するのがこの型です。
CatList
前述したCatenable Listです。
bind
に渡した関数は、上記のExpF
に包まれて、このデータ構造に追加されます。
-- ~~~~~~~~~~~~~~~~~
data Free f a = forall b. Free (FreeView f Val b) (CatList (ExpF f))
ついでにFree
で使われているCatList
の関数をこの場で紹介しておきましょう。
-
empty :: forall a. CatList a
空のCatList
を作る -
cons :: forall a. a -> CatList a -> CatList a
要素をリストの先頭に追加 -
snoc :: forall a. CatList a -> a -> CatList a
要素をリストの末尾に追加(consを逆に読んだのか) -
uncons :: forall a. CatList a -> Maybe (Tuple a (CatList a))
リストを、最初の要素と残りのリストからなるタプルに分解する。 -
append :: forall a. CatList a -> CatList a -> CatList a
2つのCatList
を結合する(CatList
は型クラスSemigroup
のインスタンスになっており、Semigroup
の関数append
の実装はこのappend
になっているので、関数<>
を使ったときはこのappend
が呼ばれる)
さあ、これにてようやくFree
型の定義部分の説明が終わりました。
まだまだ続きますよ。
次は、Free
のモナド関連の部分です!
Free
はモナドなのでそこを見ないわけにはいかないでしょうし、後々の説明を考えてもここは外せません。
Bind
(bind
)
超重要関数bind
です。
定義を見てみましょう。
instance freeBind :: Bind (Free f) where
bind :: forall a b. Free f a -> (a -> Free f b) -> Free f b
bind (Free v s) k = Free v (snoc s (ExpF (unsafeCoerceBind k)))
where
unsafeCoerceBind :: forall a b. (a -> Free f b) -> Val -> Free f Val
unsafeCoerceBind = unsafeCoerce
まずv
(FreeView
)の部分に着目してください。新たなFree
が作られていますが、v
は何の操作もされずそのまま引き継がれていっています。
(FreeView
にはBind
があるのにそっちが使われないのは意外かもしれませんが、こっちはまた別に使われます)
次にs
(CatList
)を見てください。これはnewtype ExpF f = ExpF (Val -> Free f Val)
という定義のExp f
のリストでした。このリストに対し、bind
に渡された関数k
をsnoc
関数でもって末尾に追加しています。その際unsafeCoerce
を使って型を合わせています。
(unsafeCoerce
は無理やり型を合わせる関数。それゆえ慎重に使う必要がある。)
存在量化できなかったためこのようなことをやっているのです。
ちなみに先に説明したExists
も結局は隠蔽した値を使う際は内部でunsafeCoerce
を使っています。
とにかく渡された関数k
はCatList
に追加されるんだなということを覚えておいてください。
Applicative
(pure
)
bind
ときたら次はpure
でしょう!
定義を見てみましょう。
instance freeApplicative :: Applicative (Free f) where
pure :: forall a. a -> Free f a
pure = fromView <<< Return
Return
とfromView
の合成関数に渡された値を適用させています。
Return
の定義は頗るシンプルなので特に疑問はわかないでしょう。
data FreeView f a b = Return a | Bind (f b) (b -> Free f a)
となると問題はfromView
です。
FreeView
からFree
に変換するやつ (fromView
)
なんか『ちいかわ』みたいな見出しにしてみましたが、fromView
は小さいし、かわいいと言っても差し支えない関数なのではないでしょうか。
これが定義です。
fromView :: forall f a. FreeView f a Val -> Free f a
fromView f = Free (unsafeCoerceFreeView f) empty
where
unsafeCoerceFreeView :: FreeView f a Val -> FreeView f Val Val
unsafeCoerceFreeView = unsafeCoerce
bind
のときと同じく、unsafeCoerce
を使って型をVal
にしてやって、Free
の型にマッチさせています。つまりf
に対しては何の操作も行われていません。
次にFree
のCatList
の部分を見るとempty
関数の結果が渡されています。
つまり、渡されたFreeView
と、空のCatList
からFree
を作って返すのがこの関数です。
fromView
の動きがわかったので、pure
の動きもわかるでしょう。
つまり、pure
はこんな感じの値を返します。
Free (Return 値) 空のCatList
Functor
(map
)
これがmap
の定義です。
instance freeFunctor :: Functor (Free f) where
map :: forall a b. (a -> b) -> Free f a -> Free f b
map k f = pure <<< k =<< f
pure <<< k =<< f
の部分ですが、括弧で括ってわかりやすくすると、(pure <<< k) =<< f
となります(演算子の優先順位的は逆束縛より関数合成の方が高いため)。
ここで逆束縛によりbind
が使われています。
つまりbind f (pure <<< k)
です。
bind
とpure
の定義をまとめて見てみましょう。
bind :: forall a b. Free f a -> (a -> Free f b) -> Free f b
pure :: forall a. a -> Free f a
k
である(a -> b)
とpure
の合成関数はa -> Free f b
となるでしょう。
これはつまりbind
の(a -> Free f b)
と一致します。
更にmap
の引数のFree f a
はbind
の引数と一致します。
それゆえ、pure <<< k =<< f
でmap
の実装ができているのです。
bind
とpure
とmap
がわかったので、次はFree
を作るところにいきましょう。
liftF
でデータ型をFree
に持ち上げる
Free
を使う際は、なんらかのデータ型をliftF
で持ち上げてFree
を作ります。
サンプルではこのようにliftF
を使っていました。
data TeletypeF a = PutStrLn String a | GetLine (String -> a)
type Teletype a = Free TeletypeF a
putStrLn :: String -> Teletype Unit
putStrLn s = liftF (PutStrLn s unit)
getLine :: Teletype String
getLine = liftF (GetLine identity)
実装はどうなっているでしょうか。
liftF :: forall f. f ~> Free f
liftF f = fromView (Bind (unsafeCoerceF f) (pure <<< unsafeCoerceVal))
where
unsafeCoerceF :: forall a. f a -> f Val
unsafeCoerceF = unsafeCoerce
unsafeCoerceVal :: forall a. Val -> a
unsafeCoerceVal = unsafeCoerce
出てきた要素を見てください。
fromView
, Bind
, Val
, unsafeXXX
, pure
すべて既出です。
つまりliftF (GetLine identity)
とした場合、このような値が返ることになります。
(CatList
のところで書いた通り空のCatList
は説明のため配列のように[]
と置いています)
Free (Bind (GetLine identity) pure) []
bind
呼び出すとどーなるの?
では前項でFree
型の値の形がわかったところで、次はそれらを使って次のようにbind
を呼び出したときどうなるかを見ていきます。
example :: Teletype Unit
example = do
a <- getLine
putStrLn a
bind
の定義と、liftF
で作られるFree
型の値を使って考えると次のようなイメージになるでしょう。
図:値が使われる様子
最終的には、次のようにCatList
に関数が追加された新たなFree
が返されます。
Free (Bind (GetLine identity) pure) [ExpF (\s -> Free (Bind (PutStrLn s unit) pure) [])]
この例では一つだけbind
で処理を繋ぎましたが、これ以上増やした場合も同じで、CatList
の末尾に関数が追加されていくことになります。
Free
の実行 〜その裏で起きているコト〜
ここまでで、実行に使うFree
を作るまでの説明が終わりました。
いよいよ作ったFree
がどう実行(解釈)されるのかを説明していきたいと思います。
今一度冒頭で例示したサンプルコードを見てみます。
teletypeN :: TeletypeF ~> Effect
teletypeN (PutStrLn s a) = const a <$> log s
teletypeN (GetLine k) = pure (k "fake input")
run :: Teletype ~> Effect
run = foldFree teletypeN
echo :: Teletype Unit
echo = do
a <- getLine
putStrLn a
main :: Effect Unit
main = do
run echo
echp
で返されるTeletype Unit
(Free TeletypeF Unit
)が実行対象のFree
です
teletypeN
はフリーモナドでおなじみのハンドラ部分ですね。
このハンドラはfoldFree
でどう呼び出されるのか?
その呼び出しの裏で何が起きているのか?
そこを解説していきます。
先に書いておきます。
・・・・・・長い!複雑!
でも解説します。
foldFree
まずfoldFree
はこんな定義になっています。
foldFree :: forall f m. MonadRec m => (f ~> m) -> Free f ~> m
foldFree k = tailRecM go
where
go :: forall a. Free f a -> m (Step (Free f a) a)
go f = case toView f of
Return a -> Done <$> pure a
Bind g i -> (Loop <<< i) <$> k g
この関数を理解するには、関数冒頭のtailRecM
の部分と、toView
の部分の理解が必要となります。
なので、先にそれぞれを説明します。
tailRecM
tailRecM
はMonadRec
という末尾再帰の際にスタックを大量消費しないことを表す型クラスの関数です。
foldFree
の定義を見ると、MonadRec m
の制約があり、そして返される型がm
になっています。
これは(f ~> m)
が返す型と一致しています。
foldFree :: forall f m. MonadRec m => (f ~> m) -> Free f ~> m
foldFree k = tailRecM go
where ...
動作的には単純で、tailRecM
に渡したa
に対し、関数(a -> m (Step a b))
を実行し、Step
の値がLoop a
であればa
の値を使ってループし、Done b
であればm b
を返すという動きをします(当然インスタンスによってやり方は異なる)。
data Step a b = Loop a | Done b
class Monad m <= MonadRec m where
tailRecM :: forall a b. (a -> m (Step a b)) -> a -> m b
ところで、上記の例でfoldFree
に渡している関数はteletypeN :: TeletypeF ~> Effect
という型の関数でした。つまりこの場合m
はEffect
となります。
Effect
はMonadRec
のインスタンスになっているため使うことができるのです。
ちなみに今回の例の場合は関係ない話(なので飛ばしても結構です)なのですが、Free
もまたMonadRec
型クラスのインスタンスになっています。
これがどういうことを意味するかというと、foldFree
に渡す引数をteletypeN :: TeletypeF ~> 別のFree
というようにできるということです。
instance freeMonadRec :: MonadRec (Free f) where
tailRecM :: forall a b. (a -> Free f (Step a b)) -> a -> Free f b
tailRecM k a = k a >>= case _ of
Loop b -> tailRecM k b
Done r -> pure r
-- bindの定義
bind :: forall a b. Free f a -> (a -> Free f b) -> Free f b
まず最初にk a
とした結果はFree f (Step a b)
となります。
その次にbind
が呼び出されます。
bind
の(a -> Free f b)
の部分は、上記のコードのcase
の部分を見ると、Step a b -> Free f b
なので、型にマッチしています。
処理的にはStep
の値がLoop
である限りはtailRecM
を再帰的に呼び出し、値がDone
になったらpure r
でFree f b
型の値を返すようになっています。
Free
からFreeView
に変換するやつ (toView
)
なんかまた『ちいかわ』みたいな見出しですが、『ちいかわ』とは違って、この関数は小さくもかわいくもないです。
toView :: forall f a. Free f a -> FreeView f a Val
toView (Free v s) =
case v of
Return a ->
case uncons s of
Nothing ->
Return (unsafeCoerceVal a)
Just (Tuple h t) ->
toView (unsafeCoerceFree (concatF ((runExpF h) a) t))
Bind f k ->
Bind f (\a -> unsafeCoerceFree (concatF (k a) s))
where
concatF :: Free f Val -> CatList (ExpF f) -> Free f Val
concatF (Free v' l) r = Free v' (l <> r)
runExpF :: ExpF f -> (Val -> Free f Val)
runExpF (ExpF k) = k
unsafeCoerceFree :: Free f Val -> Free f a
unsafeCoerceFree = unsafeCoerce
unsafeCoerceVal :: Val -> a
unsafeCoerceVal = unsafeCoerce
まずcase v of
でv
(FreeView
)をパターンマッチにかけます。
それぞれのパターンを説明します。
Bind
だった場合
Bind
だった場合は、新しいBind
を返しています。
その際f
はそのまま引き継いで使われます。
次に(\a -> unsafeCoerceFree (concatF (k a) s))
の説明をしましょう。
Bind
の定義は、Bind (f b) (b -> Free f a)
ですが、Free
のデータ構築子で使われる際は(FreeView f Val Val)
という定義になっていました。
すなわちBind (f Val) (Val -> Free f Val)
です。
なのでBind f k
のk
は(Val -> Free f Val)
です。
そして(\a -> unsafeCoerceFree (concatF (k a) s))
のa
はVal
です。
なのでk a
はFree f Val
を返してきます。
concatF
では、一つ目の引数のFree f Val
のVal
の部分すなわちCatList
と、二つ目の引数のCatList
を<>
で結合させて返します。その際、Free f Val
のf
はまたそのまま引き継ぎます。
ちなみにconcatF
の二つ目の引数に渡していたs
とは、toView
を呼び出したときのFree
が持っていたCatList
です。
そしてこのCatList
にはbind
関数が呼ばれたとき継続の処理が追加されていたのでした。
その値がFree (FreeView f Val Val) (CatList (ExpF f))
のCatList
から、FreeView
の方に移されて返っているということなのです。
bind
を使ったときの説明の例で出てきた次のような値
Free
(Bind (GetLine identity) pure)
[ExpF (\s -> Free (Bind (PutStrLn s unit) pure) [])]
に対して、toView
を呼び出した場合は次のようになるでしょう。
Bind
(GetLine identity)
(\a -> concatF (pure a) [ExpF (\s -> Free (Bind (PutStrLn s unit) pure) [])]))
ということで、FreeView
に変換してもCatList
の内容は残っているということなのです。
Return
だった場合
Return
だった場合、Free
の持っているs
(CatList
)をuncons
でh
(head)とt
(tail)のTuple
に分解しています。
h
とはnewtype ExpF f = ExpF (Val -> Free f Val)
のことで、t
はそのリストです。
concatF ((runExpF h) a) t
の部分では、(runExpF h) a
の結果、すなわち(Val -> Free f Val) a
の結果であるFree f Val
とt
を引数にconcatF
を呼び出しています。
CatList
が保持している関数が呼び出されるのは、説明においてここが初ですね。
Bind
のときのconcatF
とは異なり、こちらの場合はuncons
によって一つ関数が消費された状態のリストが結合されることになります。
そうしてできた値をtoView
に渡して再帰します。
この再帰呼び出しはs
が空になるまで続けられ、s
が空になったらようやくReturn
が返って処理が終わります。
これがReturn
の場合の処理です。
以上が、toView
の説明になります。
ざっくり要約して書くとこんな感じでしょうか。
-
Free
をFreeView
にして返す。 -
Free
が持つFreeView
がBind
だったら新しいBind
を返す。その際、Free
が持っていたCatList
の内容は、新しいBind
の方に(関数の中で使われるという形で)移動する。 -
Free
が持つFreeView
がReturn
だったら、Free
が持つCatList
をuncons
でhead要素の関数とtailのリストに分解し、head要素の関数を適用した結果(とtailのリストを結合したもの)で再帰呼び出しをする -
Free
が持つFreeView
がReturn
でかつCatList
が空の場合は、Return
を返す。
なのでtoView
に渡したFree
のFreeView
がReturn
だったとしても、Bind
が返ってくる可能性があります(CatList
が持っている関数の結果がBind
かもしれない)。
続・実行の解説
tailRecM
とtoView
の説明が終わったので、foldFree
の動きも理解できるでしょう。
ということで、解説に必要なコードを再掲した上で、本格的に実行時の処理の流れの解説をしましょう。
以下が解説に必要なコードです。
data TeletypeF a = PutStrLn String a | GetLine (String -> a)
type Teletype a = Free TeletypeF a
putStrLn :: String -> Teletype Unit
putStrLn s = liftF (PutStrLn s unit)
getLine :: Teletype String
getLine = liftF (GetLine identity)
teletypeN :: TeletypeF ~> Effect
teletypeN (PutStrLn s a) = const a <$> log s
teletypeN (GetLine k) = pure (k "fake input")
run :: Teletype ~> Effect
run = foldFree teletypeN
echo :: Teletype Unit
echo = do
a <- getLine
putStrLn a
main :: Effect Unit
main = do
run echo
foldFree :: forall f m. MonadRec m => (f ~> m) -> Free f ~> m
foldFree k = tailRecM go
where
go :: forall a. Free f a -> m (Step (Free f a) a)
go f = case toView f of
Return a -> Done <$> pure a
Bind g i -> (Loop <<< i) <$> k g
toView :: forall f a. Free f a -> FreeView f a Val
toView (Free v s) =
case v of
Return a ->
case uncons s of
Nothing ->
Return (unsafeCoerceVal a)
Just (Tuple h t) ->
toView (unsafeCoerceFree (concatF ((runExpF h) a) t))
Bind f k ->
Bind f (\a -> unsafeCoerceFree (concatF (k a) s))
-- unsafe系の関数やrunExpFの定義は省略
この例ではecho
が返すFree
の値をfoldFree teletypeN
に渡しています。
echo
が返す値はこのようになっています。
Free
(Bind (GetLine identity) pure)
[ExpF (\s -> Free (Bind (PutStrLn s unit) pure) [])]
foldFree
のgo
関数はDone
を返すまで、すなわちtoView f
がReturn
を返してくるまで再帰的に呼び出され続けます。
この再帰的な処理をステップごとに順々に追っていきたいと思います。
1. toView
(1回目)
上記の値(echo
が返す値)をf
としてtoView f
が呼ばれます。
toView (Free v s) =
case v of
Bind f k ->
Bind f (\a -> unsafeCoerceFree (concatF (k a) s))
v
の値はBind
だったのでBind f k
にマッチします。
なので次のような値が返ってきます。
Bind
(GetLine identity)
(\a -> concatF (pure a) [ExpF (\s -> Free (Bind (PutStrLn s unit) pure) [])])
2. case toView f of
のパターンマッチ(1回目)
go f = case toView f of
Bind g i -> (Loop <<< i) <$> k g
上記toView
の結果はBind
なので、Bind g i
のパターンにマッチします。
そしてg
は(GetLine identity)
、 i
は(\a -> concatF (pure a) ...)
となります。
処理としてはまずk g
が呼び出されます。
3. k g
の処理(1回目)
k
は処理を遡ってみればteletypeN
だとわかります。
teletypeN :: TeletypeF ~> Effect
teletypeN (PutStrLn s a) = const a <$> log s
teletypeN (GetLine k) = pure (k "fake input")
なのでk g
はteletypeN g
となりますね。
g
はteletypeN (GetLine k)
にマッチしk
はidentity
(getLine
を参照)なので、pure (identity "fake input")
が返るでしょう。
更に書くとidentity
はそのまま値を返すのでこれはpure "fake input"
です。
pure
はEffect
のpure
なのでEffect String
型の値が返ります。
4. (Loop <<< i) <$> k g
の処理(1回目)
k g
の結果はEffect String
型の値pure "fake input"
だったので、Effect
のmap
が呼ばれます。
map
に渡される合成関数の最初の関数i
とは
(\a -> concatF (pure a) [ExpF (\s -> Free (Bind (PutStrLn s unit) pure) [])]))
でした。
今回のa
は"fake input"
なので
concatF (pure "fake input") [ExpF (\s -> Free (Bind (PutStrLn s unit) pure) [])]
となるでしょう。
そしてpure "fake input"
は、Return "fake input" []
です。
これに対しconcatF
が呼ばれてCatList
の内容が結合され
Free (Return "fake input") [ExpF (\s -> Free (Bind (PutStrLn s unit) pure) [])]
という値になり、更にi
はLoop
と合成されていたので
Loop (Free (Return "fake input") [ExpF (\s -> Free (Bind (PutStrLn s unit) pure) [])])
となります。
map
関数はEffect
のものであったので正確には上記の値はEffect
に包まれていますね。
(これはtailRecM
が戻り値の型として期待していたm (Step a b)
とマッチしています)
この値がループにより再帰に使われます。
5. toView
(2回目)
ループして再度toView f
にやってきました。今度のf
は
Free (Return "fake input") [ExpF (\s -> Free (Bind (PutStrLn s unit) pure) [])]
という値になっています。
これに対してtoView
を呼び出すとどうなるか。
toView (Free v s) =
case v of
Return a ->
case uncons s of
Nothing ->
Return (unsafeCoerceVal a)
Just (Tuple h t) ->
toView (unsafeCoerceFree (concatF ((runExpF h) a) t))
まずCatList
であるs
は今回は空でないのでuncons s
で分解すると次の値を持つJust (Tuple h t)
になります。
h = ExpF (\s -> Free (Bind (PutStrLn s unit) pure) [])
t = []
a
は今回の場合"fake input"
で、runExpF
はExpF
が持つ関数を取り出す関数なので
(runExpF h) a
↓
(\s -> Free (Bind (PutStrLn s unit) pure) []) "fake input"
↓
Free (Bind (PutStrLn "fake input" unit) pure) []
となります。
この値でもってtoView
が再帰的に呼び出されます。
6. toView
(3回目)
ループして再度toView f
にやってきました。今度のf
は
Free (Bind (PutStrLn "fake input" unit) pure) []
という値になっています。
この値でtoView
を呼び出すとどうなるか?
toView (Free v s) =
case v of
Bind f k ->
Bind f (\a -> unsafeCoerceFree (concatF (k a) s))
はい。今回の戻り値は次のようになるでしょう。
Bind (PutStrLn "fake input" unit) (\a -> unsafeCoerceFree (concatF (pure a) []))
7.case toView f of
のパターンマッチ(2回目)
go f = case toView f of
Bind g i -> (Loop <<< i) <$> k g
上記toView
の結果はまたBind
なので、Bind g i
のパターンにマッチします。
そしてg
は(PutStrLn "fake input" unit)
、 i
は(\a -> unsafeCoerceFree (concatF (pure a) []))
となります。
処理としてはまずk g
が呼び出されます。
8. k g
の処理(2回目)
k
とはteletypeN
でしたね。
teletypeN :: TeletypeF ~> Effect
teletypeN (PutStrLn s a) = const a <$> log s
teletypeN (GetLine k) = pure (k "fake input")
となると、今回のg
はteletypeN (PutStrLn s a)
にマッチするので、const unit <$> log "fake input"
が呼び出されます。
log "fake input"
でログ出力がされるとEffect Unit
型の値が返され、それに対してmap
関数が呼ばれます。
つまり(\b -> const unit) <$> log "fake input"
ということなので、const
によりunit
がそのま返されEffect Unit
型の値が返ります。
9. (Loop <<< i) <$> k g
の処理(2回目)
k g
の結果はEffect Unit
型の値unit
だったので、Effect
のmap
が呼ばれます。
map
に渡される合成関数の最初の関数i
は(\a -> unsafeCoerceFree (concatF (pure a) []))
でした。
今回のa
はunit
なので
concatF (pure unit) []
となるでしょう。そしてpure unit
は、Return unit []
です。
これに対しconcatF
が呼ばれCatList
が結合された次のFree
となります(空同士の結合なので結果は空)。
Free (Return unit) []
更にi
はLoop
と合成されていたので
Loop (Free (Return unit) [])
となります(これは本当はEffect
に包まれています)。
この値がループによりまた再帰に使われます。
10. toView f
(3回目)
今回はLoop (Free (Return unit) [])
に対してtoView
が呼ばれます。
toView (Free v s) =
case v of
Return a ->
case uncons s of
Nothing ->
Return (unsafeCoerceVal a)
Just (Tuple h t) ->
toView (unsafeCoerceFree (concatF ((runExpF h) a) t))
CatList
は空なので、uncons s
でこれ以上分解できません。
それゆえ今度はNothing
のパターンにマッチします。
ということはReturn unit
が返されるということです。
11. case toView f of
のパターンマッチ(3回目)
今度はようやくReturn a
にマッチするようになりました。
go f = case toView f of
Return a -> Done <$> pure a
a
はunit
なのでEffect
に包まれたDone unit
が返ります。
Done
を返しているので遂にここでループは終了します。
最終的にはEffect Unit
型の値unit
が返ります。
以上の処理の流れで、echo
の値に着目し、値がどのように変化していったかを書いてみます。
Free
(Bind (GetLine identity) pure)
[ExpF (\s -> Free (Bind (PutStrLn s unit) pure) [])]
-- ↓ toView
Bind
(GetLine identity)
(\a -> concatF (pure a) [ExpF (\s -> Free (Bind (PutStrLn s unit) pure) [])])
-- ↓ ハンドラ(teletypeN)の呼び出し。ここで入力が与えられ、処理の結果以下が返る。
Free
(Return "fake input")
[ExpF (\s -> Free (Bind (PutStrLn s unit) pure) [])]
-- ↓ toView (CatListの要素が残っているので以下のFreeでtoViewを再帰呼出し)
Free
(Bind (PutStrLn "fake input" unit) pure)
[]
-- ↓ toView
Bind
(PutStrLn "fake input" unit)
(\a -> unsafeCoerceFree (concatF (pure a) []))
-- ↓ ハンドラ(teletypeN)の呼び出し。ここで値がログ出力され、処理の結果以下が返る。
Free
(Return unit)
[]
-- ↓ CatListが空なので値が返って処理終了
Return unit
まとめると次のような流れになっていますね。
-
toView
するとFreeView
が返る。 -
FreeView
がBind f b
なら、f
を使ってハンドラを呼び出す。 - ハンドラを実行結果は
Bind
が持っている関数(b -> Free f a)`の引数として使われ関数が呼び出される。 - 上記の結果また新しい
Free
が返ってきて、それがまたtoView
に渡って再帰する。 -
FreeView
がReturn a
なら-
CatList
の先頭の関数をa
を引数として呼び出す。結果はFree
なのでtoView
を再帰 -
CatList
が空ならReturn a
を返す
-
わかりやすいかわかりませんが、頑張って流れを図解してみます。
まとめ
まずFree
を作るliftF
がこのような値を返してきます。
Free (Bind (GetLine identity) pure) []
pure a
はFree (Return a) []
のような値を返す関数で、これはBind (f b) (b -> Free f a)
の(b -> Free f a)
の部分になっています。
つまりliftF
が作るFree
のBind
は常にReturn
を返す関数を持っているということです。
これがミソです。
実行していったときこのReturn
が持つ値が、CatList
が持つ先頭の関数の引数になっているからです。
後続の処理に繋ぐための橋渡しをするというかくっつける糊的存在というか、そんな感じです。
例えば、bind
で処理を繋げて次のような値になった場合、pure
が返すReturn
の値がExpF
の関数の引数になっているわけですね。
Free
(Bind (GetLine identity) pure)
[ExpF (\s -> Free (Bind (PutStrLn s unit) pure) [])]
つまりFree
のFreeView
はCatList
の先頭の関数に処理を繋ぐことができ、その関数はまた同じような構造のFree
を返してきて(かつCatList
の先頭の関数は除去される)、そのFree
のFreeView
からCatList
の先頭の関数に処理が繋がって、、、、
というように(bind
で繋いだ関数がすべてなくなるまで)繰り返されるというわけです。
それにしても、bind
で繋いでいく後続の処理を「(整列された)関数のシーケンス」と考え、パフォーマンスの良いデータ構造に持っておき、実行のとき取り出して使うというアイデアが実現されているのを見てきたわけですが、よくこんなやり方を思いついたものだと思います。
さぁ以上で、ようやく、ようやく、実行の解説が終わり、この記事の目的を果たすことができました。
_人人人人人人人人人人人人人_
> 長かった戦いよさらば!! <
 ̄Y^Y^Y^Y^Y^YY^Y^Y^Y^Y^Y^ ̄
終
私はPureScriptの学び始めの頃、いきなりこれを理解しようとしてエラい苦労した記憶があります。
前提知識もなかったし、勘所もなかったからです。
写経もしましたが、それでもよくわからなかった。
最初にシンプルなフリーモナドの実装で、おおまかに構造を理解していればまた違ったのでしょう。
(そういう意味で前の記事を書いた)
このような経験があったため、ある程度まとまった記事があれば、同じ道を辿らなくて済む人が増えると思い、今回の記事を書きました。
どの程度PureScriptのフリーモナドに関心がある(しかも実装まで)人がいるかわかりませんが、少しでも理解の助けになっていれば幸いです。
Free
でReader
モナドを作ってみるよ
おまけ: foldFree
は、ハンドラを使って結合されていたすべてのFree
を一気にまとめて処理しましたが、Free
のレイヤーを一枚一枚剥がしながら実行するための関数resume
というものがあります。
resume:resume
:: forall f a
. Functor f
=> Free f a
-> Either (f (Free f a)) a
resume = resume' (\g i -> Left (i <$> g)) Right
resume'
:: forall f a r
. (forall b. f b -> (b -> Free f a) -> r)
-> (a -> r)
-> Free f a
-> r
resume' k j f = case toView f of
Return a -> j a
Bind g i -> k g i
これを使って、Free
のReader
モナドを作ってみます!
newtype ReaderF r e = ReaderF (r -> e)
derive newtype instance functorReaderF :: Functor (ReaderF r)
type FreeReader r a = Free (ReaderF r) a
ask :: forall e. FreeReader e e
ask = liftF (ReaderF identity)
local :: forall r a. (r -> r) -> FreeReader r a -> FreeReader r a
local f r = map f ask >>= pure <<< runReader r
asks :: forall e a. (e -> a) -> FreeReader e a
asks f = f <$> ask
-- ここでresumeを使っているよ
runReader :: forall r a. FreeReader r a -> r -> a
runReader f e = case resume f of
Left (ReaderF r) -> runReader (r e) e
Right a -> a
こちらがテストになります!
type Config = { debug :: Boolean }
spec :: Spec Unit
spec = do
describe "Reader(Free版)のテスト" do
describe "ask" do
it "環境を取得できる" do
"value" `shouldEqual` runReader ask "value"
describe "asks" do
it "環境を取得する際に渡した関数で環境の値を変更することができる" do
"value added" `shouldEqual` runReader (asks (_ <> " added")) "value"
describe "local" do
it "環境の変更を、渡した関数内のスコープに閉じることができる" do
let
getFlag :: FreeReader Config Boolean
getFlag = do
_ <- local (\c -> c { debug = true }) do
-- ここでaskするとdebugはtrueになってる。
pure false -- 説明のためだけの処理なので適当な値を返す
c <- ask
pure c.debug
runReader getFlag { debug: false } `shouldEqual` false
Discussion