そういえば先程、
※あれ、:-で連鎖って、なんだか>>=っぽいですよね…?
とか言ってました。
実際に>>=に置き換わったのはMaybeが出てきてからですが、それ以前でも-:と>>=の類似性は気になるところです。
Zipperの多くの関数は概ね
Zipper a -> Zipper a
というシグネチャになっていました。
さらに考えると、実はこれらの関数は「変更前のZipperを受け取り、変更後のZipperを返す」というものです。
つまり、Zipperの状態遷移が起こっていると考えられるのですが、状態遷移と言えばState…。
はい、EXTRA STAGE突入です。
Zipperの状態をStateで管理させれば、いちいち関数の戻り値として返す必要は無くなりそうです。
import qualified Control.Monad.State as S
goLeft :: S.State (Zipper a) ()
goLeft = do
(Node x l r, bs) <- S.get
S.put (l, LeftCrumb x r:bs)
goRight :: S.State (Zipper a) ()
goRight = do
(Node x l r, bs) <- S.get
S.put (r, RightCrumb x l:bs)
newFocus :: S.State (Zipper a) ()
newFocus = do
goLeft
goLeft
goRight
main :: IO ()
main = do
print $ S.runState newFocus (freeTree, [])
Stateを用いることによって、goLeft/goRightがdo記法で利用できるようになりました。
S.State (Zipper a)
という型が何度も現れるので、これを改めてZipperとして定義しましょう。
type Zipper a = S.State (Tree a, Breadcrumbs a)
goLeft :: Zipper a ()
...
goRight :: Zipper a ()
...
newFocus :: Zipper a ()
...
さらに、topMost/modify/attachを定義してみましょう。加えて、現在の注目点の部分木を返す関数があれば、実際に操作するのに便利なので それをgetFocusとして定義します。
topMost :: Zipper a ()
topMost = do
(t, bs) <- S.get
case bs of
[] -> return ()
otherwise -> do
goUp
topMost
modify :: (a -> a) -> Zipper a ()
modify f = do
(t, bs) <- S.get
case t of
(Node x l r) -> S.put ((Node (f x) l r), bs)
Empty -> return ()
attach :: Tree a -> Zipper a ()
attach t = do
(_, bs) <- S.get
S.put (t, bs)
getFocus :: Zipper a (Tree a)
getFocus = do
(t, _) <- S.get
return t
newFocus :: Zipper Char ()
newFocus = do
goLeft
goLeft
goRight
modify (\_ -> '@')
goLeft
attach (Node '*' Empty Empty)
t <- getFocus
goLeft
attach t
topMost
main :: IO ()
main = do
print $ S.runState newFocus (freeTree, [])
さて、そもそものZipperの役割は「木構造の効率の良い操作」なのですが、これまでのコードでは、 初期状態としてわざわざBreadcrumbsの空リストを渡したり、結果にもBreadcrumbsがくっついています。更に言えば、操作後の木全体が欲しいのが通常なので、そのためにいちいちユーザにtopMostを指定させるのも手間です。
Zipperのユーザには、Breadcrumbsという実装の事情は隠蔽したいものです。また、結果も自動的に全体を返すようにすればなお便利。 そんな関数runZipperを定義しましょう。
runZipper :: Zipper a () -> (Tree a) -> (Tree a)
runZipper m t = fst $ S.execState (m >> topMost) (t, [])
newFocus :: Zipper Char ()
newFocus = do
goLeft
goLeft
goRight
modify (\_ -> '@')
goLeft
attach (Node '*' Empty Empty)
t <- getFocus
goLeft
attach t
main :: IO ()
main = do
print $ runZipper newFocus freeTree
ここにきて、Zipperとは、DSLとしてgoLeft/goRight等の命令セットをユーザに提供し、それを用いてユーザが記述した処理を実行して、木構造を操作するフレームワークとなりました。Haskellにおけるモナドの役割は、このようなDSLを定義するフレームワークとなることが主だったりします(もちろんそれ以外の役割もあります)。
さらに言えば、Zipperの影響範囲はrunZipperが境目になっています。Zipperの状態遷移という副作用はrunZipperの内側に局所化され、その外側に漏れ出すことはありません。
手続き型言語では、グローバル変数を筆頭に、このような「副作用の影響範囲」というものがあやふやでしたが、Haskellはモナドを用いることで、副作用の範囲を明確に定義することができます。
本編では、ZipperをMaybeで包むことによって、失敗を表現していました。
しかし、今回は既にStateを用いているために、そのままMaybeで包みこむと、>>=がStateとしての役割を失ってしまいます。折角StateでZipper再構築しても、失敗が綺麗に扱えなくては、本編のZipperよりも魅力を感じません。
あるモナド計算の中で、他のモナドを並行して使いたくなるケースは実際良くあります。
そのような、>>=に2つのモナドの能力を持たせるために用意されているのがモナド変換子(monad transformers)です。
http://hackage.haskell.org/package/transformers
モナド変換子は「基盤となるモナド」と「掛け合わせるモナド」の2つで構成されています。 そのため、基盤となるモナド毎に、モナド変換子が存在します。命名規則として、基盤となるモナドの名前にTを付加しています。
- StateT
- ReaderT
- WriterT
- etc...
今回は、StateTを用いて、Maybeと掛け合わせます。StateTは、下記のような定義です。
newtype StateT s m a = StateT { runStateT :: s -> m (a,s) }
上記のmの部分に、掛け合わせたいモナドを指定します。runStateTの結果は、掛け合わせたモナドで包まれたStateの最終状態です。
早速、StateTでZipperとgoLeft/goRightを実装してみましょう。
type Zipper a = S.StateT (Tree a, Breadcrumbs a) Maybe
goLeft :: Zipper a ()
goLeft = do
(Node x l r, bs) <- S.get
S.put (l, LeftCrumb x r:bs)
goRight :: Zipper a ()
goRight = do
(Node x l r, bs) <- S.get
S.put (r, RightCrumb x l:bs)
newFocus :: Zipper a ()
newFocus = do
goLeft
goLeft
goRight
main :: IO ()
main = do
print $ S.runStateT newFocus (freeTree, [])
変更したのは、StateTにしてMaybeを掛け合わせたくらいで、goLeft/goRight自体は全く変わっていません。 一方、runStateTの実行結果はJustに包まれています。
それでは、失敗した場合を実装してみましょう。
goLeft :: Zipper a ()
goLeft = do
(t, bs) <- S.get
case t of
Empty -> S.lift Nothing
(Node x l r) -> S.put (l, LeftCrumb x r:bs)
goRight :: Zipper a ()
goRight = do
(t, bs) <- S.get
case t of
Empty -> S.lift Nothing
(Node x l r) -> S.put (r, RightCrumb x l:bs)
newFocus :: Zipper a ()
newFocus = do
goLeft
goLeft
goLeft
goLeft
goLeft
モナド変換子にて、掛け合わせたモナドの値を戻り値にする場合には、関数liftを用いる必要があります。 上記の場合、liftを用いて、NothingをMaybe aからStateT s Maybe aに持ち上げています。
なお、掛け合わせたモナドがIO場合には、特別な関数liftIOが用意されていますので、通常はこちらを用います。
第14章で、Writer型の実装は公開していない、とありました。ここで、現在のStateの定義を見てみましょう。
type State s = StateT s Identity
モナド変換子StateTに対して、モナドIdentityを掛け合わせたものが、現在のStateの定義です。 Identityとは「何もしない」モナドです。モナド変換子に何もしないモナドを掛け合わせることで、基盤となるモナドの性質のみを提供しています。 多くのモナドは、概ね上のような「モナド変換子+Identity」のスタイルで定義されています。