あどけない話

インターネットに関する技術的な話など

型クラスとモナドと Free モナド

要約:Free モナドは何が嬉しいのかを議論するためのたたき台。以下の2つの論文に載っている例を3つの方法で実装する。

  • Janis Voigtlander, "Asymptotic Improvement of Computations over Free Monads"
  • Wouter Swierstra and Thorsten Altenkirch, "Beauty in the Beast -- A Functional Semantics for the Awkward Squad"

モナド

最近、僕はモナドを次のように説明するようにしている。「モナドとは言語内DSLを実装するための API (あるいはフレームワーク)」

だから、何か言語内DSLを作るなら、それをモナドインスタンスにすべきだ。ここでは、getChar と putChar という API を持つ簡単な DSL を考える。この DSL を CharIO と呼ぼう。

当然、入出力なので IO の中で走るべきだが、表現と解釈は分離したい。
つまり getChar/putChar という表現と、解釈系を分離する。解釈系には

  • 実際に IO の中で走らせる
  • 副作用を発生させずに走らせる

の2つを考える。後者は純粋だから、QuickCheck でテストする。

2つの点に注意:

  • 作った DSLモナドだから do が使える。返り値も持つ。
  • CharIO で実装する echo は無限ループする。EOF エラーが発生すると止まる。これを純粋にどう実装するのか?

型クラス

Real World Haskell の 15 章には、型クラスで実装する方法が載っている。CharIO という型クラスのメソッドが getChar/putChar という訳だ。IO を CharIO のインスタンスにすれば、IO の中で走るし、純粋なモナドを CharIO のインスタンスにすれば、純粋に実行できる。それを実装したのがこのコード

感想:

直接のモナド

やはり何らかのデータ構造を定義して、それをモナドにしたい。その実装がこれ

感想:

  • データ型に本質でない Pure という構成子が必要なのでちょっと嫌。
  • 純粋に走らせる方は、簡単に書けた。

Free モナド

Free モナドを使うとこうなる。

感想:

  • Pure は、Free モナドで共通化されるので不要になる。
  • 型の様式も実装の様式も少し簡単になる。

追記:DeriveFunctor 拡張を使えば、Functor の定義が不要になる。

議論

どの方法でも、やりたいことは一応実装できる。「直接のモナド」を使ってもよいが、「Free モナド」だと、ほんの少しだけ簡単になる。他の利点は何だろう?