Zenn
🐙

Haskellで状態操作

に公開
Haskell
tech

前回の記事で C# を用いたIOモナドの実装を紹介しました

以前に触れたように、 Haskell は巨大なクロージャを作る言語です
これは仮の表現ではなく、実際にIO型の内部にはひとつの関数オブジェクトが定義されています

newtype IO a =IO (State# RealWorld ->
 (# State# RealWorld, a #))

この関数は戻り値にタプルを返します
C# の実装では、# State# RealWorldはstruct IO<A>に属するプロパティとして表していますが、実際には実引数として用いる# RealWorldをクロージャの実行毎に生成し、型変数aとセットで管理します

C#のIO構造体
public interface IIOControl<out A>{
    internal Func<object,A> Function{get;}
    internal object RealWorld{get;}
}

public struct IO<A>:IIOControl<A>{
    internal IO((Func<object,A>,object) @value)=>_value=@value;
    readonly (Func<object,A> function,object realWorld) _value;
    Func<object,A> IIOControl<A>.Function=>_value.function;
    object IIOControl<A>.RealWorld=>_value.realWorld;
}

このタプルの第一要素は状態を表現するパラメータとして扱われます
原則的にアクセスは許されず、特定の型クラスに属するいくつかの構造体を介して操作することになります

この型クラスこそがモナドであり、そのインスタンスとして振る舞う構造体の一種が状態系モナドです
例えばState型は以下のように定義されます

newtype State s a = State
{ runState :: (s -> (a,s)) }

これは仮引数をタプルの第二要素に変換する関数を保持する構造体です
例えばこの構造体の定義に倣ってIO構造体を書き下すと以下の形に置き換えられます

IO a =IO (State# RealWorld ->
 (# a, State# RealWorld #))

つまりタプルの第一要素を第二要素に移すことで状態の取得を可能とします
State# RealWorldはランタイムの仕様として取り出しが禁止される構造体であるため、実際にこの実装を実現することは不可能ですが、IOモナドと状態系モナドの等価性が伺えます

タプルの第一要素はクロージャの線形再帰ストリームに則って以前のモナドから次のモナドへとバトンされます
その実態はオブジェクトの複製あるいは参照のリレーであり、初期値となる実引数がクロージャに渡されることによって一連のロジックが連動します

クロージャの特性を利用すれば、そのロジックをユーザー側で実装することも可能です
重要なポイントは、State# RealWorldがIntなどの汎用的な型に置き換え可能であるという着想です

IOモナドをそのまま利用することはできないので、ここでは仮の構造体Fを考えます

newtype F a=F (Int->(Int,a))

IntはState# RealWorldの代替です
そもそもState#とは型変数付きの構造体であり、同様の定義を模倣するならば、以下のように実装されます

newtype F a=F (Int->(Int,a))
newtype R a=R (F Int->(Int,a))

Fは関数オブジェクト付き構造体なので、Rの構造を考えると定義が複雑化します
ここではFのみを使用します

Fでは、状態を表すデータ型がIntであるため、これは通常タプルに隠蔽されます
結果の確認時にはこれを取得する必要があるため、Intを第二要素へ遷移させる構造体を用意しておきます

newtype S a b=S (a->(b,a))

この定義はまさしくState s a = State { runState :: (s -> (a,s)) }と等価です
違いはrunStateの有無ですが、あくまで模倣であるため今回は関数オブジェクトのみを保持します

Fを用いてIntの値を変化させる手続きを実装します

(@@)::F a->(a->F b)->F b
(F a)@@f=F $ \ x->
  (\ (f,(x,y))->
   (\ x (F a)->a (x+1)) x (f y)) (f,a x)

(@@)::F a->(a->F b)->F bは(>>=)のプロトタイプ形式に倣っています

class Monad m where
  (>>=)  :: m a -> (a -> m b) -> m b

(@@)は二つの関数で構成されます
定義に沿って整理すると、以下のように分解が可能です

(F a)@@f=F $ \ x -> pair (f,a x)
pair (f,(x,y))=record (x,f y)
record (x,(F a))=a $ x+1

Fの持つ関数オブジェクトのシグネチャによって、戻り値は(x,y)のタプルであることが保障されます
パターンマッチでタプルを分解することにより関数fの実引数yを用意し、fの戻り値であるF aの関数オブジェクトaに実引数xをあてがうことで新しいタプルを生み出します

このクロージャはコンストラクタFのシグネチャにより戻り値がタプルで制約されるので、その辻褄を合わせています
辻褄合わせの過程で、(a->F b)の関数が実行されます
その間タプルの第一要素はクロージャの引数xに束縛され、いくつかの関数を経た後に新たなFの関数オブジェクトの実引数として移譲されます
そして移譲時にx+1が評価され、値が更新されます

@@を呼び出す度に、クロージャは入れ子となり、新しいFの関数オブジェクトへ丸ごと渡されます
この関数は、あくまでクロージャを形成する手続きであることに留意してください
このように、状態をクロージャで包むことで純粋性を維持します

xの遷移は表現できましたが、この手続きではxを取り出せません
そこで、先ほど定義した構造体Sを使用します
xをタプルの第二要素へ移動させ、printで標準出力へ渡すためIO Intとして返します
Fを簡易的に生成する関数makeも併せて作成します

newtype S a b=S (a->(b,a))

put (F a)=S $ \ x->
 (\ (x,y)->(y,x)) $ a x

get (S a)= \ x->
 (\ (x,y)->return y) $ a x
 
pop f=get (put f) 0
make x=F (\ a->(a,x))

getはタプルの第二要素を取り出す関数ですが、戻り値は引数付きの関数オブジェクトであるため、実引数を指定する必要があります
そのためpopでは初期値に0を与えています

ここでは元々タプルの第一要素に隠されていた値が第二要素と交換されている点に注目してください
つまり、本来(# State# RealWorld, a #)におけるaに相当していた値は捨てられることになります

では、実際にこのロジック群を用いて、Intの値が遷移していく様子を追ってみましょう

main = print=<<pop (make 5@@ 
 \ x->make (x+5)@@ \ x->make x)

2

make 5で生成された値が捨てられ、状態を表していたタプルの第一要素の値を取得していることが見て取れます
この初期値はpop f=get (put f) 0で指定された0となります
この0を# State# RealWorldに置き換えれば、それがIOモナドの全体像として捉えられます

以下はここまで作成したサンプルコードの全体です

main = print=<<pop (make 5@@ 
 \ x->make (x+5)@@ \ x->make x)

newtype F a=F (Int->(Int,a))
{-newtype R a=R (F Int->(Int,a))-}

(@@)::F a->(a->F b)->F b
(F a)@@f=F $ \ x->
  (\ (f,(x,y))->
   (\ x (F a)->a (x+1)) x (f y)) (f,a x)

newtype S a b=S (a->(b,a))

put (F a)=S $ \ x->
 (\ (x,y)->(y,x)) $ a x

get (S a)= \ x->
 (\ (x,y)->return y) $ a x
 
pop f=get (put f) 0
make x=F (\ a->(a,x))
{-
(F a)@@f=F $ \ x -> pair (f,a x)
pair (f,(x,y))=record (x,f y)
record (x,(F a))=a $ x+1
-}

ところで、構造体RはF Intを持っていました

newtype R a=R (F Int->(Int,a))

Fは関数オブジェクトを持っていたので、すなはちこれは(Int,Int)を戻り値に持つ関数を引数に取ることと同義です

ここでFとRを新しく生成し続けるクロージャを考えれば、タプルを多層的に管理できるでしょう
Haskell ではこのようにパターンマッチとタプルを組み合わせることで状態のカプセル化と受け渡しを実現しています

クロージャはタプルの初期値となる引数を最初に受け付けることでその値を更新できるようになります
その更新可能な値の一つとしてRealWorldも数えられており、IOは同様のロジックでRealWorldの複製を渡し続けるのです

名前の通り、それは常に状態更新を繰り返す現実世界を表すシンボルとなっています
しかし、それはあくまで模倣です
そこにはただ実体のない構造体と Haskell の言語的機構があるのみで、IOという不可避な副作用という名の状態はクロージャという衣をまとって確かにそこに在るのです

Discussion