yunomuのブログ

趣味のこと

Stateモナドとモナドトランスフォーマー

Haskell

前フリ

最近@seizansさんが新人Haskell使いを増やしまくっている。
で、その人達がググった時のために先にたくさんブログ記事書いて釣ろうぜっていう話をしていたけど、@kazu_yamamotoさんとか@nom4476さんらが仰るように、一旦自分がわかってしまうとなかなか記事を書く気力が起きない（し、子育てで忙しいので後は任せたって言われた）。
そうこうしているうちに@seizansさんがすごい勢いでHaskell力を伸ばしはじめた。
なので最近彼が覚えたらしいモナドトランスフォーマーの入門的な記事をStateモナドと合わせて先回りして書いてしまおうというわけす。引用数を稼ぐには先手必勝です。

Stateモナド

Haskellで一時的な状態を持たせたい時はStateモナドを使うらしいですよ。
といっても何が何だかよくわかんないんですけど、
状態モナド遊び - あどけない話
この記事を見て、ほとんど何をやってんだかよくわかんないんだけど、一番最後の

ここまで理解できれば、これはStateモナドの再発明だったと気付くことでしょう。

というところだけわかった。いや「ここまで」の部分はなんかあんまし理解してないんですけど。
コードを引用すると、このへん

import Control.Monad.State

type Counter = Int
data List a = Nil | Cons a (List a) deriving Show

cons :: a -> List (Counter, a) -> State Counter (List (Counter, a))
cons x xs = do cnt <- get
               put (cnt + 1)
               return (Cons (cnt, x) xs)

evalState (cons "c" =<< cons "b" =<< cons "a" Nil) 0
→ Cons (2,"c") (Cons (1,"b") (Cons (0,"a") Nil))

つまりStateの定義をこんな感じとすると（本当はtypeですが）

data State s a

aはまあなんか、値というか、処理結果の値というか、そういうの。
で、sが状態、途中経過を格納する部分。
"State s"までがMonadで、この中のsの部分を操作するための関数がgetとかputという、それだけの話なんでしょう、使う分には。

これを使えばもっとかっこよくスタックが作れるかもしれない！　sにスタックの現在の状態を保存しておけばいいわけだね。
と思いついて、三度dcっぽいものが登場します。
一度目：Haskellでdcっぽいのを作る その1 - yunomuのブログ
二度目：Haskellでdcっぽいのを作る その2 型安全とは - yunomuのブログ

たぶん、こういう感じに

State [a] a

sの部分にスタック形式のデータ（っていうかリストですけど）を入れておくようにするとうまくいくんじゃないかなぁ。

dcのためのスタックを書いている時、一度目二度目の時はどうにもこの中の「スタックから値を2つ取り出して計算してスタックに格納」とか、そういう処理がかっこよく書けなくて、それがずっと頭の片隅にあったんですけど、
Stateを使ってpushとpopをこう書けばいいんじゃない？

push :: a -> State [a] ()
push a = do
    as <- get
    put (a:as)

pop :: State [a] a
pop = do
    as <- get
    f as
  where
    f []     = fail "stack empty"
    f (a:as) = do
        put as
        return a

で、電卓側でこれを使う時はこうなる。
値を2つ取り出して計算する場合、

ope :: Stack Int -> (Int -> Int -> Int) -> Stack Int
ope s f = execState (do
    v1 <- pop
    v2 <- pop
    push $ f v1 v2
  ) s

Applicativeスタイルにすると

ope :: Stack Int -> (Int -> Int -> Int) -> Stack Int
ope s f = execState (f <$> pop <*> pop >>= push) s

かっこいい。

今回はスタックの例なのでexecStateとか使ってますけど、runStateとかevalStateの方がよく使うような気がする。そこら辺は適当に調べて使ってください。
ということで、Stateモナドというのはだいたいこういう風に使うんじゃないでしょうか。

まあそれはいいんですけど、
実を言うとこのdc ver.3は、さっきのState版だと実は機能がver.2相当からver.1相当に劣化している。

ver.3というか上記のコードではpopでスタックが空の時にfailを実行しているんだけど、これは実は内部でerrorを呼んでたりして、ランタイムエラーになっちゃうんですよね。そのおかげで画面表示するまでスタック操作が評価されなくて、スタックが空になるタイミングで演算子を入力しても、例えばいきなり(1 +)とか入力しても、画面表示コマンド(p)を実行するまでエラーが出ない。

つまりスタックの操作というのは実は状態も持っているけど失敗する可能性のあるデータの操作でもあるわけで。
そこでモナドトランスフォーマーというのが出てくるのです。

モナドトランスフォーマー

Haskellでは「失敗する可能性のある操作」はMaybeとかEitherで表現します。こいつらもモナドのインスタンスです。そしてStateもモナドです。
というのを踏まえつつ、

先ほどの「状態を持ちつつ失敗する可能性のあるデータ」というのは、上のスタックの例でそのまま考えると

State [a] (Maybe a)

とかそういう感じになるかと思われますが、
こういう風に複数のモナド（この場合はStateとMaybe）を組み合わせて使う機会というのは結構多いらしく、そういう時に便利なライブラリがあります。
それがモナドトランスフォーマーというらしいです。（mtl, transformersパッケージ）

モナドトランスフォーマーはなんかすごそうな名前ですけど、見た目は普通のモナドの値の部分に単にモナドが入るというだけのもので、さっきと同じ例で言うとこんなかんじになる。

StateT [a] Maybe a

まあ、StateがStateTになって、Maybeに付いてたカッコが無くなるだけです。意味はほとんど同じです。
それと、モナドはトランスフォーマーになると末尾にTって付くらしいです。MaybeTとかListTとか。
つまりモナドトランスフォーマーはモナドを値として持つモナドってことですね。mapMとかと同じ感覚です。

これを使って書きなおしたpushとpopはこんな感じになります。

push :: a -> StateT [a] Maybe a
push a = do
    as <- get
    put (a:as)

pop :: StateT [a] Maybe a
pop = do
    as <- get
    f as
  where
    f []     = lift Nothing
    f (a:as) = do
        put as
        return a

型定義の部分のStateにTって付けて、値にMaybeを付けただけです。
あーあと"fail"の部分が"lift Nothing"になってます。って何気にここ重要なんですが、割とどうでもいい気もします。そういうものです。それ以外は同じです。

要するに内部側のモナド（この例ではMaybe）を扱いたい場合は頭にliftって書けばいい。Stateと同じ流れで書けるわけです。そういう認識でとりあえず間違い無いと思います。

もちろん実行する側もちょっと変わります。

ope :: Stack Int -> (Int -> Int -> Int) -> Maybe (Stack Int)
ope s f = execStateT (f <$> pop <*> pop >>= push) s

execStateがexecStateTに変わっただけ……ではなく、戻り値の型がMaybeになります。
途中で失敗していたらNothingが返ってきますので、外側でよしなに処理してあげてください。

だいたいこんな感じですね。
これがStateとMaybeを組み合わせて利用したい時の動きで、あとはこれの型の組み合わせが変わるだけです。
IOモナドを使う時はまたなんとかとかあるみたいですが、だいたいモナドトランスフォーマーでググったりするとIOが絡んだ時の例で解説されてたりするので、適当にググるといいんじゃないでしょうか。

今回遊んでみたソースはGithubに置いてます。こっちではMaybeじゃなくてEighterを使ってますが。(dc3, Stack3)と(dc4, Stack4)が今回の例に近い感じです。
exercises/dc_haskell at master · yunomu/exercises · GitHub

あとがき

いい加減これでスタックは終わりだろう。「スタック作れ」って問題出されてからもう10ヶ月近く経ってるぞ。いい問題だなぁこれ。
という感じですね。
いやほんとこれ、start haskell第0回の時になんとなく考えたネタだったんですが、こんなに遊べるとは思いませんでした。dcを選んだ理由は「構文解析しなくていいから」だったんですけど、Haskellだと構文解析する方が圧倒的に楽なんですよね。それが身にしみてわかりました。

ということで、Haskell初心者には「dcコマンド（というか逆ポーランド記法の電卓）を作れ」って言うといいと思います。
日本人には逆ポーランド記法が向いてるので普通に便利に使えますし。使って気に食わなければ直せばいいし。
それくらいのテンションでいいと思います。

あと、さらっと「わかんない」って言って飛ばしましたけど、「状態モナド遊び」の記事は、実装部分は抜きにしてもじっくり読むと「純粋関数型で手続き的な処理をどう実現しているのか」とか、モナドというモノがベルトコンベアに喩えられたりプログラマブルセミコロンとか言われたりする意味とか、「値で貫く」とか言われている感覚とかがなんとなく理解できるような気がします。IOは1行毎に世界が変質しているのです。

その辺の感覚がわかってしまえば何も恐くありませんね。
恐くなくなる前に文章にしておくとさらにいいと思います。