Sansan Tech Blog

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

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

開発

はじめに

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

今回は一風変わったモナド、逆状態(反転状態)モナドが面白かったのでHaskellにおける状態モナドと合わせて2部構成で紹介したいと思います。

すごいH本を読んだことのある方を想定していますが知らない方にも雰囲気だけ感じ取っていただけるように紹介したつもりです。状態モナドを知っている方は後編からお読みください。

状態計算

どのようなプログラミングパラダイムにおいても、状態をどのように取り扱うかは大きなテーマです。 プログラミング言語で利用する関数の実引数や関数内で利用する一時変数なども、一種の状態として見なせるものがあります。 状態を扱う際に直面する課題は「どこで状態を持っているのかが不明」「状態の取りうる値が不明」「どこで状態が変わったか不明」などがあると思います。

今回は一つの方法として、状態を用いながら変化させつつ値を計算するものを状態計算と呼び、状態モナドとして抽象化し安全にプログラミングを行う方法の紹介を行います。(恣意的な説明も多分に含まれていますのでご注意ください。)

状態計算 (State s) モナド

今回は状態を用いて計算を行い状態を変化させるものを状態計算と呼び、その特徴を関数の型として定義します。 状態計算を行う関数の型は「状態を受け取って結果として値と次の状態を返す関数」とします。さらにその関数自体を値としてもつデータ構造を考えます。 状態計算の型定義は簡略化すると以下になります。

--newtype 型名 型変数... = 値コンストラクタ名 { フィールド名 :: 型 }
newtype State s a = State { runState :: s -> (a, s) }

newtype宣言は型エイリアスの定義とほぼ同じですが、フィールドの型と内部表現が同じでコンパイル時には新規の型として区別される文法です*1。フィールドはゲッターやセッターのようにも機能します。 s -> (a, s) は s を受け取ってタプル (a, s) を返す関数の型を表します。 s を状態の型、 a を結果の値の型と見れば、状態から値と状態を計算する関数と見ることができます。

状態計算の例としてカウンター(カウンタ値を受け取り現在の値と次のカウンタを返す関数を含んだ)のような状態計算を考えてみます。

let increment = State $ \s -> (s, s + 1)

increment :: State Int Int という型*2で runState increment 1 は (1, 2) となります。 runState :: State s a -> s -> (a, s) 関数に increment を適用するとフィールドの関数 Int -> (Int, Int) が返されます。その関数に初期状態として 1 を適用することで結果のタプルが得られます。 以上で状態計算を他のコードから分離して状態を明示的に扱うことができるようになりました。

状態計算を行うことは可能になりましたが、今のままでは状態を扱う計算を State $ \s -> ... のように一つの関数にまとめて記述する必要があります。すなわち同じ状態を利用する計算を繋げることはできません。では、状態を明示的に扱うことを維持したままに、小さな計算を繋げて大きな計算を構築する手段を実装しましょう。

恣意的な説明ですが、結果を他の値に変える性質を持たせたり、状態計算の結果の値としての関数に他の状態計算の結果の値を適用できる性質を持たせることで、柔軟に計算を行うことができます。また、状態計算の値に依存して新たな状態計算を構築できるとさらに応用が効くはずです。それらはHaskellにおいてファンクターやアプリカティブ、モナドと呼ばれるクラスとしての定義を行うことで可能になります。

状態計算のファンクターとしの定義を紹介します*3。ただの状態計算を結果の値も持ったコンテナとして、中の結果の値を変換するだけのものです。

instance Functor (State s) where
    -- fmap :: (a -> b) -> State s a -> State s b
    fmap f mx = State $ \s0 ->
        let (x, s1) = runState mx s0 -- 状態計算に状態s0を適用する
        in (f x, s1)               -- 結果の値xを関数fに適用しておく

アプリカティブとしての定義を紹介します。結果の値(関数)に結果の値を適用することが可能になるような定義です。 最初に適用された状態 s0 を変化させながら s1 と引き継いで最後の s2 を結果の状態としています。

instance Applicative (State s) where
    pure x = State $ \s -> (x, s) -- 結果の値を持つだけの状態を変化させない状態計算
    -- (<*>) ::State s (a -> b) -> State s a -> State s b
    mf <*> mx = State $ \s0 ->
        let (f, s1) = runState mf s0 -- 初期状態s0で計算した結果の関数fと計算後の状態s1
            (x, s2) = runState mx s1 -- 状態s1で計算した結果の値xと計算後の状態s2
        in (f x, s2) -- f に x を適用し、次への状態はs2とする

モナドとしての定義です。これは依存した状態計算を繋げるために実装します。 有名な >>= :: Monad m => m a -> (a -> m b) -> m b は、m a がもつ a から m b を計算し(そのままでは m (m b) となるところを) m b にできるというモナド則の一部です*4。

instance Monad (State s) where
    -- (>>=) :: State s a -> (a -> State s b) -> State s b
    mx >>= f = State $ \s0 -> -- s0 を受け取り (b, s2) を返す関数で状態計算を定義する
        let (a, s1) = runState mx s0 -- 状態計算 mx に s0 を適用した結果を(a, s1)とする
            (b, s2) = runState (f a) s1 -- f へ a を適用した結果の状態計算に s1 を適用して (b, s2) とする
        in (b, s2)

以上で状態計算を抽象的に定義して柔軟に扱うことができるようになりました。先ほどの increment も

runState (increment >> increment) 1 == (2, 3)

のように、同じ状態の型を扱う状態計算をつなげていくことができるようになります。

次の話題としては「状態モナドの利用ケース」「更に抽象化したクラス」「状態の取りうる値」などがありますが、また別の機会があれば紹介したいと思います。

次回へ

ここまで、s -> (a, s) を持つようなデータを状態計算と呼んできました。繋げ方は暗黙的に上記の定義を選びましたが、必ずしも同じ方法で定義しなくてもいいはずです。 次回は他の繋げ方を選ぶことで一風変わった状態計算を定義することができる逆状態(反転状態)モナドを紹介していきます。 「モナドは単なる自己関手の圏におけるモノイド対象だよ。何か問題でも？ 」で有名なWadlerさん*5がThe essence of functional programmingの 2.8 Variation six: Backwards state で逆方向に状態計算を進める方法を提示されているので次回紹介したいと思います。

*1:新規の型として扱われることによる多彩な応用もあるのですが今回は説明しません。興味がある方へは @mr_konn さんの 本当はすごいnewtype@speakerdeck が面白いです。

*2:正確には Num a => State a a という多相関数ですが簡単のためにIntを用います。

*3:State s のような型のFunctorは自動導出することが可能です。12.6.4.1. Deriving Functor instances

*4:実用面でのモナドを知るには 箱で考えるFunctor、ApplicativeそしてMonad @ Qiitaの翻訳記事が分かりやすいです。

*5:Lambda Man: https://corecursive.com/021-gods-programming-language-with-philip-wadler/

© Sansan, Inc.