トップ «前の日記(2009-06-12) 最新 次の日記(2009-06-14)» 月表示 編集

日々の流転


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 ではないだろと思った。

関連