日々の流転

λ. Typed Logical Variables in Haskell. Koen Claessen, Peter Ljunglöf

• <URL:http://jp.citeulike.org/article/310660>

を読んだ。

論理型言語をHaskellに埋め込む話。そのために必要なのは論理変数とバックトラッキングで、型のある論理変数を実現するのにSTRefを使っている。バックトラキングはバックトラックを実装するモナドトランスフォーマーをSTの上に重ねて実現。STRefに書き込む部分では、バックトラックするときに元の値に戻すようにしておく。まあ、当たり前の方法を当たり前に実装したという印象。

バックトラッキングを実装するモナドトランスフォーマーは簡単な実装が示されているだけで、効率的な実装については Ralf Hinze の論文を参照とのこと。その辺りは Backtracking, Interleaving, and Terminating Monad Transformers とも比較してみるべきか。