2009-06-13 [長年日記]
λ. “Data types á la carte” by Wouter Swierstra
を読んだ。これは以下を使って、いわゆる Expression Problem を解決する話。
- 明示的な不動点の構成
- data Expr f = In (f (Expr f))
- シグニチャ関手の埋め込みを表す型クラス
- class (Functor sub, Functor sup) ⇒ sub :<: sup where inj :: sub a → sup a
- 定義したい関数毎の型クラス
例えば、式の型に乗算を追加して、それを扱えるように評価関数を拡張するには、以下のようなものを書くだけで良い。
data Mul x = Mul x x instance Functor Mul where fmap f (Mul x y) = Mul (f x) (f y) -- スマートコンストラクタ infix 7 ⊗ (⊗) :: (Mul :<: f) ⇒ Expr f → Expr f → Expr f x ⊗ y = inject (Mul x y) instance Eval Mul where evalAlgebra (Mul x y) = x*y
ちょっと、「へぇ」と思ったのは、data Term f a = Pure a | Impure (f (Term f)) で定義されるモナド Term f は自由モナドだけど、Term自身もモナドの圏から関手の圏への忘却関手の左随伴になっているという意味で自由、という話。
あと、オーバーラップするインスタンスを使うから Haskell 98 じゃないと言っているけど、そもそも f :<: g という多引数の型クラスを使っている時点で Haskell 98 ではないだろと思った。