Sansan Tech Blog

Sansanのものづくりを支えるメンバーの技術やデザイン、プロダクトマネジメントの情報を発信

状態を扱うモナド(後編)

開発

前回のおさらい

どうも、改めましてプロダクト開発部の自称社内関数型担当の福田です。社内でのHaskellの本を読む勉強会を運営しています。

前回は状態を扱う関数を状態計算と定義し、小さな状態計算を連鎖できるような構造を持たせるための定義を行いました。「これで安心安全に状態計算が行える！」と喜び勇んで数多の状態計算を実装しまくるところですが、今回は少し目線を変えた定義を行うことで一風変わった状態計算の表現になる逆状態モナドを紹介します。 前回に比べてHaskellの文法要素も増えるので遅延評価に倣って逆状態モナドが必要になったときに以下を読むことをお勧めします*1。

状態モナド

前回紹介した状態計算を繋げる方法としてApplicativeとMonadのインスタンス定義を行いました。復習も兼ねて一部抜粋します。

instance Applicative (State s) where
    pure x = State $ \s -> (x, s)
    mf <*> mx = State $ \s0 ->
        let (f, s1) = runState mf s0
            (x, s2) = runState mx s1
        in (f x, s2)
instance Monad (State s) where
    mx >>= f = State $ \s0 ->
        let (a, s1) = runState mx s0
            (b, s2) = runState (f a) s1
        in (b, s2)

<*> と >>= は2つの状態計算を合成可能にし、より大きな状態計算の構築を可能にしています。 ポイントは渡された最初の状態 s0 が演算子の左側(第1引数)の状態計算によってs1に、続けて右側の状態計算で s2 へと連鎖しているところです。

逆状態モナド RState s モナド

今まではどの順序で状態を変化させるかを暗黙的に決めていましたが、逆の方向に変化させても問題はないのではないかと疑ってみます。

変化の方向を反転させて連結を行う状態計算を RState s a (Reversed State)として定義してみましょう。 フィールドの型やFunctorのインスタンス定義までは State s a と全く同じになりますがApplicativeやMonadとしての定義が異なります。

{-# LANGUAGE DeriveFunctor #-}
newtype RState s a = RState { runRState :: s -> (a, s) } deriving (Functor)

instance Applicative (RState s) where
    pure x = RState $ \s -> (x, s)
    mf <*> mx = RState $ \s2 ->
        let (f, s0) = runRState mf s1
            (x, s1) = runRState mx s2
        in (f x, s0)

instance Monad (RState s) where
    mx >>= f = RState $ \s2 ->
        let (a, s0) = runRState mx s1
            (b, s1) = runRState (f a) s2
        in (b, s0)

前回の State との対比のために runRState 関数の仮引数名を s2 と命名していることに注意してください。

<*> と >>= は最初に渡された状態 s2 を演算子の右側の状態計算に適用して変化後の状態 s1 を左側の状態計算へ伝播させています。 Applicativeとしての定義は状態が逆に伝播しているため奇妙ではあるかもしれませんがそれだけで大きな問題には見えません。しかし、Monadとしての定義はより奇妙に見えます。それは、s0, s1, s2 の計算順序と a, b の計算順序が交差している点です。 (a, s0) の計算が s1 に依存しており、(b, s1) は f a に依存しているので、 a と s1 で依存関係が再帰しています。 値は前方から後方に向けて計算されますが、状態は後方から前方へ向けて計算されるため、値の計算順序に依存関係があるモナドではこのように循環が起きてしまいます。

日常的に状態は順方向に伝播していくものと捉えていると許しがたいかもしれませんが、ここまでは定義できているということで百歩譲って(Haskellの文法的な意味で)許してください。許したとしても実際にどのような計算を表現することができるのかは考える必要がありそうです。

応用

逆状態モナドは何の役に立つのか、プロダクトで応用できるケースがあるのか、どのような性質を持っているのか、応用できそうなケースを少し考えてみます。 状態操作を扱うのは前提として、通常の状態モナドが適していると思われていたケースで取って代わる、もしくは併用するとシンプルに書けることがあるかもしれないです。または、状態を扱う局面でとりあえず使ってみるというのがいい戦略かもしれません。

以下に応用できそうなシーンをいくつか紹介しますが他にもまだまだ応用例があると思います。見つけた場合はぜひ教えてください。 逆状態モナドの世界が花開くことを期待しています。

逆畳み込み

走査可能な構造 Traversable に対して、構造で定義された走査の方向とは逆方向で畳み込みを行うケースです。 これは実際にHaskellの標準ライブラリ base にもほぼ同じ実装でmapAccumRとして登場しています。 外部からは逆状態モナドの利用は隠して内部のフィールドの型 s -> (b, s) を受け取るように記述されています。

mapAccumR :: Traversable t => (a -> s -> (b, s)) -> s -> t a -> (t b, s)
mapAccumR f s t = runRSstate (traverse (\a -> RState (f a)) t) s
-- traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)

型が長くて分かりにくいので利用例を見てみましょう*2。リストから逆方向に累積和の列を生成する例です。

let _ = mapAccumR (\a s -> (s + a, s + a)) 0 [1..10]
-- ([55,54,52,49,45,40,34,27,19,10], 55)

状態操作と畳み込みを行う関数 \a s -> (s + a, s + a) を用いて 初期状態 0 で [1..10] に対して右から畳み込みを行っていることがわかるかと思います。

逆状態モナドを用いずに愚直に実装すると反転してから累積和を計算し再度反転することになるので少しお得かもしれません*3。 ちなみに、traverse がApplicativeの制約まででモナドの制約は要求していないことにも注目です。

シングルパス

入力の後方から得られる状態を利用する処理を記述するケースです。 The essence of functional programming; 2.8 Variation six: Backwards state

This example may seem contrived, but this monad arises in practice. John Hughes and I discovered it by analysing a text processing algorithm that passes information both from left to right and right to left.

と非常に簡単に紹介されています。

テキスト処理の際に「入力すべてを読むことで得られる状態」を「入力から得られる構造」から参照する必要があるケースで活用できます。実質二度の走査が必要になるところを状態モナドと逆状態モナドを併用することで、双方向の状態操作を可能にしシングルパス(入力1度の走査)で表現できます。

http://kcsongor.github.io/time-travel-in-haskell-for-dummies/ ではアセンブラにおけるラベルのアドレス解決を tardis ライブラリ*4で定義された構造を用いて紹介されています。

Tardisモナドと同様の構造を今回は新たに State として定義してみます*5。 ApplicativeとMonadの定義は素直に組み合わせるだけで、ヘルパー関数の実装も簡単なので割愛します。ぜひ手元で実装を与えてみてください。

module Control.Monad.BidirectionalState
    ( State
    , runState
    , evalState
    , getForwards
    , modifyForwards
    , getBackwards
    , modifyBackwards
    ) where

newtype State fw bw a = State { runState :: (fw, bw) -> (a, (fw, bw)) }
-- instance Applicative (State fw bw) where ...
-- instance Monad (State fw bw) where ...
getForwards :: State fw bw fw
getBackwards :: State fw bw bw
modifyForwards :: (fw -> fw) -> State fw bw ()
modifyBackwards :: (bw -> bw) -> State fw bw ()
evalState :: State fw bw a -> (fw, bw) -> a

import qualified Control.Monad.BidirectionalState as B
import qualified Data.Map.Strict as M

type Addr = Int
type SymTable = M.Map String Addr
type Assembler a = B.State SymTable SymTable a
data Instr
    = Add
    | Mov
    | ToLabel String
    | ToAddr Addr
    | Label String
    | Err
    deriving (Eq)

runAssembler :: [Instr] -> [(Addr, Instr)]
runAssembler asm = B.evalState (assemble 0 asm) (M.empty, M.empty)
    where
        assemble :: Addr -> [Instr] -> Assembler [(Addr, Instr)]
        assemble _ [] = return []
        assemble addr (Label label : instrs) = do
            B.modifyBackwards (M.insert label addr)
            B.modifyForwards (M.insert label addr)
            assemble addr instrs
        assemble addr (ToLabel label : instrs) = do
            table <- M.union <$> B.getForwards <*> B.getBackwards
            let instr = maybe Err ToAddr $ M.lookup label table
            rest <- assemble (addr + 1) instrs
            return $ (addr, instr) : rest
        assemble addr (instr : instrs) = do
            rest <- assemble (addr + 1) instrs
            return $ (addr, instr) : rest

input :: [Instr]
input = [ Add, Add, ToLabel "my_label", Mov, Mov, Label "my_label", Label "second_label", Mov, ToLabel "second_label", Mov]
expect :: [(Int, Instr)]
expect = [ (0,Add), (1,Add), (2,ToAddr 5), (3,Mov), (4,Mov), (5,Mov), (6,ToAddr 5), (7,Mov)]

main :: IO ()
main = print $ expect == runAssembler input

せっかく定義した RState を捨てることなくモナド変換子版の状態モナド StateT を用いて type Assembler a = StateT SymTable (RState SymTable) a としても関数を適切に置き換えれば動作しますので手元で試してみてください。

遅延評価

後方から得られる状態を待っていたらいつまでも計算が進まないはずですが、なぜ逆状態モナドは動作するのでしょう。 参考にした The essence of functional programming; 2.8 Variation six: Backwards state には

Lazy evaluation makes possible a strange variation: the state may be propagated backward. ... To make this change in an impure language is left as an exercise for masochistic readers.

とあるように遅延評価のおかげが大きいようです。遅延評価によって後方から得られるはずの状態の計算を先送りにしているため計算自体は次に進めることが可能になっています。 マゾヒストな読者の一人を https://pavkin.ru/reverse-state-monad-in-scala-is-it-possible/ で見かけましたが

I came to conclusion that there’s no possible way to implement flatMap for ReverseState in Scala. ... In this post we found out, that ReverseState is not a Monad in Scala. Again, I would really love to be proven wrong here, so if you happen to find a working instance – please, ping me!

Scalaにおいて依存が循環しているため逆方向の状態計算のモナドとしての実装を諦めたようです。 僕もデフォルト遅延評価でない言語でも、制約を設けて巧妙に実装すれば実装できるはずと思っています。できたらお知らせください。

まとめ

  • 状態操作について紹介
    • 前編：状態計算を型としての定義と状態計算を繋げるためモナドとして定義
    • 後編：状態計算を繋げる方向を変えた逆状態モナドの定義と応用例の紹介

逆状態モナドを実際の正格評価や逐次実行が当たり前のプログラミングで利用することは後方から状態を伝えることに莫大な手間を要するため敷居が高いかもしれません。解決策として候補に上がることはまずないでしょう。

しかし方法として知っておくことは何かの役に立つ場面があるかもしれません(ないかもしれません)。

おまけ：Reversed State の日本語訳

英語圏では reversed state と呼ばれ、一部では backword state などと呼ばれていました。 日本語に訳す際には 逆状態 か 反転状態 が候補として思いつきましたが、 逆 だけでは何が逆なのか考える余地があるので、値の計算順序に対して状態の連鎖の方向が反対という意味を含んだ 反転 が適しているように思いました。 今回は短くキーボードで入力しやすいので安直に逆状態を用いていますが個人的には反転状態の方が好みです。

*1:必要になることがなければHaskellの学習コストも払う必要はありませんのでご安心ください

*2:関数合成やその他の記述方法を用いればもう少し端的に記述できます。今回は紹介のためなのでHaskellに慣れた方には冗長かもしれませんがご了承ください。

*3:今回のテーマから逸れるので紹介しませんがRecursion schemesも面白そうですよ

*4:逆状態モナドの振る舞いをドクター・フーの次元超越時空移動装置に見立てて借用しているようです

*5:ライブラリの利用やStateTとの合成でもいいですが状態操作などが煩雑になる点や、let式を用いることで簡潔に定義できるため新たに定義します。tardisではdo構文内で反駁不可パターンが多用されていますが今回は用いなくても動作します。(というか必要なのか見極めがついていません。)

© Sansan, Inc.