Just $ A sandbox

プログラミングと計算機科学とかわいさ

Free Monadを使ってみよう!(2)

前回の記事について

前回の記事では、Free MonadをFunctorの延長として捉え、Monad的な使い方ではなくFunctor的な使い方を中心にFree Monadについて見て見ました。

さて、上の記事は実際のところ、まだFree Monadの便利さの片面しか見えていないと言わざるを得ません*1。今回はもう少しFreeな構造とMonadについて深く見ていきたいと思います。

Free Monadの定義

Free Monad 今回の記事は主にこちらのFree packageを参考に書いています。

以下にFree型の宣言とMonadインスタンスを示します。

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

instance Functor f => Monad (Free f) where
  Pure a >>= f = f a
  Free m >>= f = Free ((>>= f) <$> m)

前回も言いましたがこれをFunctorとして捉えれば、再帰的に定義されたデータ(プログラム/函数)の列それぞれに順番に作用するような函数が定義できます。

実際、

data List   a = Cons    a (List   a)  | Nil
data Free f a = Free   (f (Free f a)) | Pure a

のように捉えればFreeの構造はまさにListの構造と同じものでした。

ここで簡単な例を作ってみましょう。Freeな構造を作るためには適当なFunctorを用意する必要があります。ここではMaybeに似た Simple というデータを作っています。

import Control.Monad.Free

-- data Maybe  a      = Nothing  | Just a
data    Simple a next = End next | Data a next
                      deriving (Show)

instance Functor (Simple a) where
  fmap f (End next) = End (f next)
  fmap f (Data a next) = Data a (f next)
  
putF :: Int -> Free (Simple Int) () -> IO ()
putF n (Free (Data a next)) = do 
  putStrLn ("Data:" ++ show a)
  putF (a+n) next
putF n (Free (End _)) = do
  putStrLn "End"
  putStrLn ("Result:" ++ show n)
putF n (Pure _) = putStr "Result:" >> print n

dataF :: Int -> Free (Simple Int) ()
dataF a = liftF $ Data a ()

endF :: Free (Simple Int) ()
endF = liftF $ End ()

-- >>> putF 0 $ dataF 10 >> endF >> dataF 20
-- Data:10
-- End
-- Result:10

-- >>> putF 0 $ dataF 10 >> dataF 20
-- Data:10
-- Data:20
-- Result:30

なかなかつまらない例でしょう?putFがFree型のデータを受け取って、データの行数だけ"Data"とデータの中身を表示し、最後まで来たら全ての合計を表示します。ただし、途中にendFがあればそこで"End"を吐いて出力を終了します。

これだけでは何が嬉しいのか、という感じですが、例えばこのデータ列に影響を与える函数を定義してみましょう。例えば、データをスキップする操作を作ってみます。

-- 変更したところだけ掲載します

data Simple a next = End next | Data a next | Skip a next
                   deriving (Show)

instance Functor (Simple a) where
  fmap f (End next) = End (f next)
  fmap f (Data a next) = Data a (f next)
  fmap f (Skip a next) = Skip a (f next)
  
putF :: Int -> Free (Simple Int) () -> IO ()
putF n (Free (Data a next)) = do 
  putStrLn ("Data:" ++ show a)
  putF (a+n) next
putF n (Free (End _)) = do
  putStrLn "End"
  putStrLn ("Result:" ++ show n)
putF n (Pure _) = putStr "Result:" >> print n
putF n (Free (Skip a next)) = do
  putStrLn ("Skip " ++ show a ++ "steps.")
  putF n $ backTo a next

skipF :: Int -> Free (Simple Int) ()
skipF a = liftF $ Skip a ()

backTo :: Int -> Free (Simple Int) () -> Free (Simple Int) ()
backTo 0 x = x
backTo n (Free (Data _ next)) = backTo (n-1) next
backTo n (Free (End next)) = backTo (n-1) next
backTo n (Free (Skip _ next)) = backTo (n-1) next

tinyProgram :: Free (Simple Int) ()
tinyProgram = do
  dataF 2
  skipF 3
  dataF 2
  dataF 2
  dataF 2
  dataF 10

-- >>> putF 0 $ tinyProgram
-- Data:2
-- Skip 3steps.
-- Data:10
-- Result:12

Simple型はスキップするという情報を持たなくてはいけないのでデータの宣言を少し変えました。それに伴ってFunctorの宣言が少し変わっています。また、putFにskipをさせる処理を追加する必要があったので、backTo函数によってデータをnステップスキップします。また、今までは dataF 2 >> dataF 2 などと書いていたのを、 tinyProgram にまとめました。

すこし立ち止まって考えましょう。

私達はSimple型を定義し、それをFunctorのインスタンスにしました。よってSimpleをFunctorとして扱うことはできます。しかし、 tinyProgram の中で私達はFreeデータを モナドであるかのようにdo記法を用いています 。なぜこんなことができるのでしょうか?Free Monadの定義をもう少し良く見返しましょう。

instance Functor f => Monad (Free f) where
  return = Pure
  Pure a >>= f = f a
  Free m >>= f = Free ((>>= f) <$> m)

そうです、実はFunctorがあればFreeは自動的にMonadになります…!

これが、Free型がMonadとして非常に重宝される所以です。FunctorはMonadよりは導出しやすいですし、実際Functorを構成できればMonadのようにdo記法が使えます。

そしてdataF, endF, skipFなどをまるで「別のプログラム言語の命令であるかのように」書ける様になります。これがdoの力ですね!

さて、私達は非常に簡単にskipをするという処理を得ました。backToは同じ型のデータを受け取って処理しているだけなので、単純かつ純粋に書けます。ここではFreeの再帰的な構造によってputFが処理すべきデータが常にFree (Simple Int) ()の型で統一されているということです。Free Monadのおかげで、 tinyProgram が何行のデータになろうとも、常に同じ型として扱えるという素晴らしい性質を持っています。

これは、いわばFreeが「中が透けたデータ」になっているからです。Free型は全てのFreeの中身が同じ型であるという制約があります。その制約と引換に、どんなデータでも同じ型で統一的に函数が書けるのです!

例えばIOモナドに一度入れたものは基本的にはそれを取り出すことはできないので、一旦純粋ではなくなってしまったデータは、ずっとモナドに閉じ込められた状態で扱わなくてはなりません。しかし、Freeの構造であれば簡単に(retract :: Monad f => Free f a -> f a を使ってください)取り出すことまで可能です!

まとめ

Free Monadは見てきたように同じ型のものが再帰的に折りたたまれたようなデータです。使うときにはそれらを上手く展開して、順に作用するような函数を書けば良いことになります。さらにFree Monadはその定義から、Functorを定義してやれば勝手にMonadになります。Freeデータ型は「中の構造が透けた」純粋なデータであるので、Free Monadを上手く使えば純粋でないコードを最小限に抑えることができます。

もちろん、doを使えば「Freeなデータを与える部分(tinyProgramの部分)」と「それを解釈する部分(putFなどの部分)」を綺麗に分けることができるようになります。また、純粋な部分をできる限り多くできるのも嬉しいところですね!

Free Monadの使い方はこれだけではありません。まだまだ隠された応用がたくさんあると思います。

是非皆さんも自分の力でそれを見つけてみてください!

Happy Haskell/Pure-functional Programming with Free!

参考文献

Hackage: free package

https://gist.github.com/4557371 ... 今回組んだプログラム

*1:少し前まで私は「do記法が気持ち悪い」と思っていましたが、それは間違いであることがわかったので続編を書くことになりました