STモナド

この記事はモナド(プログラミング)の一部として作成された内容を元にしています。

STモナドとはState Transferモナドの略らしい。Haskellなどでは関数型プログラミングで禁忌とされているはずのメモリの書き換えを可能にするものとして紹介されることが多い。

概要

純粋関数型言語では、再代入を認めないのでStateモナドではflatMap_Stateのたびに新しいStateが生じることになるが、現実のプログラミングの問題として考えた場合、Stateが大きなデータ構造であった場合、関数を1回適用するたびに新しいStateを生成していたらパフォーマンスを大きく落とすことになる。そこで純粋関数型言語のまま再代入を可能にするトリックが、STモナドである。

パフォーマンスのことを考えず、メモリや処理速度が無制限に提供されるのであれば、Stateモナドで構わない。

構造

STモナドは一種のStateモナドである。上記でいうState(以下S)の部分と、Aにあたる部分があるはずだが、注意して欲しいのは、Sは添えるだけで一切使われることはなく、実際に再代入が行われるのはAの部分である。

ここにもうひとつSTRef(RefはRefferenceの略)という型(これはモナドではない)が登場する。

このSTRefは中に値を保持しており、しかもその値は書き換え可能である。これでは純粋関数型言語の原則が崩れてしまいそうだが、この型はトリッキーな性質でそれを回避している。

STRefに関しては以下の関数しか適用できない。この関数はSTモナドのflatMap_ST()の引数になりうる。

• new: AからST(S, STRef(S, A))というデータを作る。
• read: STRef(S, A)の中身のAからST(S, A)というデータを作る。
• modify: STRef(S, A)の中のAに関数適用してAの値を変更する。値を返すが、返ってくる値ST(S, ())からはAが消えている。('()'は空のデータのようなもの)
• (writeもあるが、modifyの特殊な場合に過ぎないので説明のため省略)

STRef自体は変更可能だが、値を取り出すためには一度STモナドに変換しなければならず、変換してしまうとSTRefではなくなるので、変更不可能になる。

flatMap_ST()にmodify()を入れてしまうと、値が消えて取り出せなくなってしまうので、flatMap_ST()に入れるのは、いくつかの操作を合成した関数で、途中にmodify()があっても最後はread()で値を返すものでなければならない。

STRef自体はSTモナドの中に入った状態でしか作れない。

STRef(S, A)のSが曲者で、new()で作ったST(S, STRef(S, A))からSTRef(S, A)を取り出そうとしても、もともとSに関する情報がないため、STRef(S, A)の型が定まらず取り出すことが出来ない。それでもST(S, STRef(S, A))という型が存在できるのは、ST(S, STRef(S, A))の内部構造がSに関する恒等式になっているため(実際にはSに依存した操作が存在しないということ)である。

以上の性質により、状態変更が行われているがその変更を外部から観測する手段がないという状況が出現する。バレなきゃあイカサマじゃあねえんだぜ。

意義

なお、STRefのmodify()はメモリを書き換えるわけだが、Stateモナドのように更新のたびに新しいStateをメモリ上に構成しても構わない。STモナドは状態変更するがその変更が外部から観測できないという性質を提供するだけであって、パフォーマンス改善のためにメモリの書き換えを行うかどうかはあくまでも処理系の実装の問題である。

ST(S, STRef(S, A))がよくてSTRef(S, A)がだめなことに納得が行かないと思うかもしれないが、結局のところ型付けをどのように扱うかという言語仕様に依存するところが大きい。そもそも純粋関数型言語でなければ、再代入が可能なのでこんなにまわりくどいいことは必要ない。

関連項目

• バレなきゃ犯罪じゃないんですよ
• モナド(プログラミング)
• Stateモナド
• IOモナド
• 圏論