Data types a la carteのメモ2

Posted on June 24, 2014
Tags: Haskell

データ型の定義はできるようになったので、このデータ型を評価していく。 数式の評価とはなにか。各項についての畳込みのことである。

畳み込みというとリストに限定して考えてしまいがちだけど、ここで云う畳み込みは一般のデータ構造に対して言うことのできる畳み込みである。

どのように畳み込みを定義するか。コンストラクタごとにどのようにして値に落としこむかを記述すればいい。 以下のような2つのコンストラクタがあったとする。

data Add e = Add e e
           deriving Functor
data Val e = Val Int
           deriving Functor

このAddとValからなる木を評価する場合、 以下のような関数があれば各コンストラクタについての評価はできる。

class Functor f => Eval f where
  evalAlgebra :: (Functor f) => f Int -> Int

AddVal をこのクラスのインスタンスにすると、木の子供が評価されてた時に自身をどう評価すればいいかがわかる。 例えば, evalAlgebra (Add 100 200) === 300 , Val 12 === 12 と評価することができる。

Fix (Add :+: Val)のo評価の時はこれを再帰的に行わなければならない。 以下の関数を使って再帰的に評価をする。データ型の定義はできるようになったので、このデータ型を評価していく。 数式の評価とはなにか。各項についての畳込みのことである。

畳み込みというとリストに限定して考えてしまいがちだけど、ここで云う畳み込みは一般のデータ構造に対して言うことのできる畳み込みである。

どのように畳み込みを定義するか。コンストラクタごとにどのようにして値に落としこむかを記述すればいい。 以下のような2つのコンストラクタがあったとする。

data Add e = Add e e   deriving Functor
data Val e = Val Int   deriving Functor

このAddとValからなる木を評価する場合、 以下のような関数があれば各コンストラクタについての評価はできる。

class Functor f => Eval f where
  evalAlgebra :: (Functor f) => f Int -> Int

AddVal をこのクラスのインスタンスにすると、木の子供が評価されてた時に自身をどう評価すればいいかがわかる。 例えば, evalAlgebra (Add 100 200) === 300 , Val 12 === 12 と評価することができる。

Fix (Add :+: Val)のo評価の時はこれを再帰的に行わなければならない。 以下の関数を使って再帰的に評価をする。

foldExpr :: Functor f => (f a -> a) -> Fix f -> a
foldExpr g (Fix t) = g (fmap (foldExpr g) t)

ここでのg::(f a -> a)Algebraと呼ばれる。

定義を見ればわかる通り、数式の木tの子孫について畳み込みをして、その結果についてgを適用している。 これでFix ffさえfunctorになっていれば再帰的に畳み込みができる。

Fix (Add :+: Val)について畳み込みをするには,Add :+: ValがFunctorでなければならない。 なので f :+: g をFunctorにする。

instance (Functor f,Functor g) => Functor (f :+: g) where
  fmap f (Inl l) = Inl $ fmap f l
  fmap f (Inr r) = Inr $ fmap f r

これで準備は整った。実際に評価部分を定義する。

instance Eval Add where
  evalAlgebra (Add v1 v2) = v1 + v2
instance Eval Val where
  evalAlgebra (Val v) = v

eval :: Eval f => Fix f -> Int
eval t = foldExpr evalAlgebra t

これで畳込みが記述できた!

foldExpr :: Functor f => (f a -> a) -> Fix f -> a
foldExpr g (Fix t) = g (fmap (foldExpr g) t)

ここでのg::(f a -> a)Algebraと呼ばれる。

定義を見ればわかる通り、数式の木tの子孫について畳み込みをして、その結果についてgを適用している。 これでFix ffさえfunctorになっていれば再帰的に畳み込みができる。

Fix (Add :+: Val)について畳み込みをするには,Add :+: ValがFunctorでなければならない。 なので f :+: g をFunctorにする。

instance (Functor f,Functor g) => Functor (f :+: g) where
  fmap f (Inl l) = Inl $ fmap f l
  fmap f (Inr r) = Inr $ fmap f r

これで準備は整った。実際に評価部分を定義する。

instance Eval Add where
  evalAlgebra (Add v1 v2) = v1 + v2
instance Eval Val where
  evalAlgebra (Val v) = v

eval :: Eval f => Fix f -> Int
eval t = foldExpr evalAlgebra t

これで畳込みが記述できた!

Free Monadとの関連はまた次回


comments powered by Disqus