技術

関数型言語で状態管理をするには

2023.05.17

著者：井上健太

はじめに

副作用を作らないことが特徴として挙げられる関数型プログラミングにおいて、副作用そのものである「状態」を管理することは一見すると難しいように見えます。しかしながらStateモナドを使用することによって純粋性を保ったまま簡単に状態を管理することができます。本記事ではその方法と考え方について、純粋関数型言語Haskellを使って見ていきます。

状態管理の例

例えば、ある関数の呼び出し回数を求めるプログラムを書いてみます。

ここではEuclidの互除法で最大公約数を求める関数を考えてみます。

Javaの場合

JavaでEuclidの互除法は例えば以下のように書けます。

public static int euclid(int n, int m) {
    if (m == 0) {
        return n;
    } else {
        return euclid(m,(n % m));
    }
}

この関数euclidは外部変数に影響を受けず、外部の状態を書き換えない純粋関数になります。このeuclid関数が呼び出される回数を求めたい場合、外部変数counterを使って、例えば以下のようにカウントすることができます。

static int counter = 0;

public static int euclid(int n, int m) {
    counter++;
    if (m == 0) {
        return n;
    } else {
        return euclid(m,(n % m));
    }
}

いわば変数counterは状態変数であり、Euclid関数内で変更を行っています。言い換えれば副作用を用いてカウントを行うということです。しかし、(ほぼ)全ての関数に副作用を持たない純粋関数型言語の場合はこのような実装は許されません。ではどのように記述すればいいでしょうか？

関数型言語の場合

まず、純粋関数型言語HaskellにおけるEuclid関数の実装を見てみましょう。

euclid :: Int -> Int -> Int
euclid n m =
    if m == 0
    then n
    else euclid m $ n `mod` m

純粋関数で外部状態を変化させることはできませんが、その外部変数を関数の引数として渡し、渡す変数を変更することで、擬似的に外部変数を書き換える手法があります。

上の例だと、従来の引数n,mに加えて呼び出し回数を数えるカウント変数c::Counterを追加します。

type Counter = Int

euclidCount :: Int -> Int -> Counter -> (Int,Counter)
euclidCount n m c =
    if m == 0
    then (n,c + 1)
    else euclidCount m (n `mod` m) $ c + 1

そして、返り値にそのカウント値を追加することで変更後のカウンターの値を得るわけです。

このeuclidCountを用いて関数の呼び出し回数を求めてみましょう。

まず、変数n1,m1に対してEuclid関数を用いた後、n2,m2に対しても使用した時の最終的な呼び出し数を数えてみます。

n1 :: Int
n1 = 15
m1 :: Int
m1 = 10

n2 :: Int
n2 = 24
m2 :: Int
m2 = 15

main :: IO ()
main =
    let
        (result1,counter1) = euclidCount n1 m1 0
        (result2,counter2) = euclidCount n2 m2 counter1
        counter = counter2
    in
    do
        print result1 -- 5
        print result2 -- 3
        print counter -- 8

このように書けば実装できますが、毎回counter1やcounter2みたいな変数が必要になってしまいます。実はこの問題はStateモナドを用いて解消することができます。

`State`モナドを用いて書き直す

先ほどの　euclidの例では、元の関数の型Int -> Int -> Int型からInt -> Int -> Counter -> (Int,Counter)型に変更になりました。これはもっと一般に、A_0 -> ... -> A_n -> B型の関数を外部変数の型sに対してA_0 -> ... -> A_n -> s -> (B,s)に変更している言えます。この最後の部分の型Bからs -> (B,s)型を作る部分が共通しており、実はこれを表現できる型クラスStateがあります。

newtype State s a = State {runState :: s -> (a,s)}
    {- 実際の実装は
    type State s = StateT s Identity
    とStateTを用いたものになりますが、ひとまず簡単のためこの定義を用います -}
state :: (s -> (a,s)) -> State s a
state = State
    {- これも本来の定義は
    state :: (Monad m) => (s -> (a,s)) -> StateT s m a
    state f = StateT (return . f)
    であることに注意です。
    -}

先ほどのeuclidCountをこのStateで書いてみます。

euclidSCount :: Int -> Int -> State Counter Int
euclidSCount n m = state $ euclidCount n m

と書いてもいいですが、Stateがモナドであることを利用して、Javaのコードのように記述することができます。

count :: State Counter ()
count = state $ \c -> ((), c + 1)

euclidS :: Int -> Int -> State Counter Int
euclidS n m = do
    count
    if m == 0
    then return n
    else euclidS m $ n `mod` m

このように書けば、あたかもcountが外部変数を変更する手続きのように記述することができます。

これを用いると先ほどのmain文は以下のようになります。

euclidIO :: State Counter (IO ())
euclidIO = do
    result1 <- euclidS n1 m1
    result2 <- euclidS n2 m2
    return $ do
        print result1
        print result2

main :: IO ()
main = do
    p
    print counter
    where
        (p,counter) = runState euclidIO 0

前の例のように、途中の状態を表す変数を書く必要はなくなりましたが、Stateモナドと入出力を行うIOモナドが別の層にあり、それぞれ別のモナド処理を行う必要が出てきます。

実はこれを1つのモナドにまとめることができます。

`StateT`を使う

まずモナド変換子(monad transformer)と呼ばれるものを考えます。これはモナドを受け取って、新たなモナドを返す型変換子です。

例えば、モナド変換子tはモナドmを受け取って、新たなモナドt mを返します。

実際に定義を見てみましょう。

class (forall m. Monad m => Monad (t m)) => MonadTrans t where
    lift :: Monad m => m a -> t m a

liftは持ち上げ関数と呼ばれ、定義のように元のmのモナド処理をt mの世界に持っていく役割があります。

これを踏まえてモナド変換子の1つであるStateTをみていきます。

newtype StateT s m a = StateT {runStateT :: s -> m (a,s)}
    
instance MonadTrans (StateT s) where
    lift m = StateT $ \c -> do
        a <- m
        return (a,s)

先ほどのStateモナドは任意の型sに対し、型aに対しs -> (a,s)を返す型でしたが、StateTではs -> m (a,s)を返すものになっていて、実はmを恒等モナドIdentityにしたものがStateモナドの定義になっています。

Euclid関数の例

先ほど定義したEuclid関数をStateTを使ったもので書き換えます。実際にはState sは正確にはStateT s Identityだったので、先ほどの関数をIdentityだけでなく任意のモナドmで使えるように一般化を行います。

count2 :: Monad m => StateT Counter m ()
count2 = state $ \c -> ((),c + 1)
    -- count2 = StateT $ \c -> return ((),c + 1)

euclidS2 :: Monad t => Int -> Int -> StateT Counter t Int
euclidS2 n m = do
    count2
    if m == 0
    then return n
    else euclidS2 m $ n `mod` m

変更点はそれぞれ型変数を導入しただけです。これはそれぞれ先ほどのcountとeuclidSの一般化なので、先ほどの例の定義をこれに書き換えても同じように動きます。

これを用いてmain文を書き直してみます。

euclidIO2 :: StateT Counter IO ()
euclidIO2 = do
    result1 <- euclidS2 n1 m1
    result2 <- euclidS2 n2 m2
    lift $ print result1
    lift $ print result2

main :: IO ()
main = do
    (_,counter) <- runStateT euclidIO2 0
    print counter

euclid2の部分で、先ほどモナド処理が分離していたのを同じモナドで処理することが可能になりました。具体的にはIOモナドの処理をlift関数を用いてStateT Counter IOモナドの処理に変換しています。

注意としては、先ほどの例のeuclidIOは事実上Counter -> (IO (),Counter)型だったのに対し、euclidIO2は事実上Counter -> IO ((), Counter)型になっていることです。つまり状態の返り値がIOの中に入ってしまっているのでそのまま取り出せなくなっています。これに困る場合は上の例を使えばいいでしょう。

まとめ

純粋関数型言語で状態を扱う時の考え方や方法について記述しました。

一覧に戻る

著者：井上 健太