読者です 読者をやめる 読者になる 読者になる

副作用の閉じ込めテクニック

Haskell

前説

Haskell純粋関数はよいものだ。 自然とコードのモジュラリティを高めてくれるおかげで再利用し易いコードが出来上がるし、 時には自分でも気づかなかった、本当に書きたかった実装を教えてくれさえする。 また副作用を許容しないということはある変数の値の構築に関わったプロセスを明確にするということなので、 デバッグの過程をとても簡単にしてくれる。

一方で、プログラムに状態はつきものだ。 例えばインタラクティブなソフトウェアや、データ構造に依存するアルゴリズムは常に状態とともにあるし、 そもそも普段使われる計算機は全て、内部状態を変化させることで計算を行う。 つまりソフトウェア/ハードウェアの各レベルにおいて、 状態をうまく扱う方法はプログラミングの重要な技術となる。 そんなわけで、今回は純粋関数を用いて状態とうまく付き合っていく方法について整理する。


動機

状態をともなう計算の純粋な表現は、特に複合的な場合に難しい。 例を見てみよう。 まず単純な状態計算は次のように表現される:

function :: Input -> State -> (Output, State)

返り値に出力だけでなく計算後の状態が含まれていることに注意したい。 この型の計算を反復する場合、例えばこうなる:

repetive :: [Input] -> State -> ([Output], State)
repetive [] state0 = ([], state0)
repetive (x:xs) state0 = (y:ys, stateLast) where
  (y, state1) = function x state0
  (ys, stateLast) = repetive xs state1

本質的には、状態を引き回しながら各入力にfunctionを適用しているだけなのだが、 計算過程の状態と入出力の変数が混在しているため、計算の流れが見えにくくなっていることがわかるだろう。 この例では、状態の計算の流れ(fold)と入出力の計算の流れ(map)が混ざっていることがわかりにくさの原因のような気がする。

では、この実装を隠蔽する高階関数を作ってみよう。 状態に対してfoldし、入力に対してmapする高階関数は次のように書かれる:

mapS :: (input -> state -> (output, state)) -> [input] -> state -> ([output], state)
mapS f [] state0 = ([], state0)
mapS f (x:xs) state0 = (y:ys, stateLast) where
  (y, state1) = f x state0
  (ys, stateLast) = mapS f xs state1

これを用いれば、先の関数はrepetive = mapS functionと書くことが出来て、 関数repetiveの実態が「状態を伴いつつ関数functionmapするもの」であることがわかりやすくなる。 めでたい。

さて、状態の計算ほど普遍的な計算となれば使いまわすことも増えるし、 他人に公開するソースコード中に登場させることもあるかもしれない。 そんなとき、mapSのような実装の読みくいオレオレ関数ではなくて、 共通の枠組みを用いて簡潔に記述したくなってくる。 ここで役に立つのがStateモナドである。


Stateモナド

モナドの記法を利用することで、状態を明記する煩わしさから解放される。 Stateモナド風に書けば、ちょうどmapSmapMに対応する:

import Control.Monad.Trans.State.Lazy (runState, state)

mapS = (runState =<<) . mapM . (state =<<)

ごちゃごちゃしていたmapSの実装がたった一行に。うれしい。

一方、そもそも状態の計算を関数的に書くことそのものが、可読性の意味で劣るということもあり得る。 そんなときにはmapMの変種forMを使うと、状態操作の部分をキレイに露出できる:

import Control.Monad (forM)

repetive xs = runState . forM xs $ \x -> state (function x)

最後のfunction xの部分をさらに細かく書き下せば、 foreach式の表現で状態計算を記述できることがわかるだろう。


具体例

抽象的な話ばかりではスッキリしないので、具体例を示しておく。 以下は辞書(Counter型)から連続で要素を取り出す例。 まずは再帰を使ったナイーブな実装:

import qualified Data.Map.Strict as Map
type Counter = Map.Map String Int

seqpop1 :: [String] -> Counter -> ([Maybe Int], Counter)
seqpop1 [] dict = dict
seqpop1 (key:ks) dict = (value:vs, dictLast) where
  value = Map.lookup key dict
  dict' = Map.delete key dict
  (vs, dictLast) = popByList1 ks dict'

二分木から連続で値を取り出すだけにしては記述が冗長すぎる。

次に高階関数を用いた抽象化:

seqpop2 :: [String] -> Counter -> ([Maybe Int], Counter)
seqpop2 = mapS pop where
  pop key dict = (Map.lookup key dict, Map.delete key dict) -- lookupとdeleteを状態計算の正準型にまとめる

だいぶ良くなった。何をしたいのかはすぐ読めるし、記述量が減っている。 しかしmapSの実装を読まないことにはこの関数の正確な動作がわからないし、 もっと複雑な計算ではmapSの第一引数がもっさりするかもしれない。

最後にStateモナドを用いる実装を2種:

import Control.Monad.Trans.State.Lazy (runState, state, get, modify')


seqpop3 :: [String] -> Counter -> ([Maybe Int], Counter)
seqpop3 keys = runState $ mapM pop' keys where
  pop' key = do {
    value <- Map.lookup key =<< get;
    modify' (Map.delete key);
    return value;
  }


seqpop4 :: [String] -> Counter -> ([Maybe Int], Counter)
seqpop4 keys dict = (`runState` dict) $
  forM keys $ \key -> do {
    value <- Map.lookup key =<< get;
    modify' (Map.delete key);
    return value;
  }

mapMバージョン、forMバージョンともに、 最初の再帰の例なみに記述量が多いが、 状態と値の流れがもっともわかりやすい。


まとめ

状態をともなう計算のわかりやすさと純粋さを両立する方法について、整理してみた。 特に、状態計算を高階関数として隠蔽する方法と、モナドを利用して簡潔に書く方法についてまとめた。