3

簡単な計算グラフを評価したいと思います。すべての非ターミナル ノードに 2 つの依存関係がある計算グラフのコードを作成することができました (これは任意の固定数の依存関係に簡単に拡張できます)。

{-# LANGUAGE ExistentialQuantification #-}

module Graph where

-- Have:
data Node a =
    forall u v . CalculationNode { f :: u -> v -> a
                                 , dependencies :: (Node u, Node v) }
  | TerminalNode { value :: a }

eval :: Node a -> a
eval (CalculationNode f (d1, d2)) = f (eval d1) (eval d2)
eval (TerminalNode v) = v

three :: Node Int
three = TerminalNode 3

abcd :: Node String
abcd = TerminalNode "abcd"

seven :: Node Int
seven = CalculationNode (\ s i -> i + length s) (abcd, three)

問題は、メモが任意の数の依存関係を取得できるように、このコードを拡張するにはどうすればよいかということです。

何かのようなもの：

data Node a =
    forall u_1 u_2 ... u_n . CalculationNode { f :: u_1 -> u_2 -> ... -> u_n -> a
                                             , dependencies :: (Node u_1, Node u_2, ... , Node u_n) }
  | TerminalNode { value :: a }

eval :: Node a -> a
eval = ?

これには typefamily/hlist ソーサリーが必要だと思いますが、どこから始めればよいかさえわかりません。解決策とヒントを歓迎します。

4

2 に答える 2

4

確かに、ちょっとした「魔法」を使えば、これは非常にうまく一般化できます。

{-# LANGUAGE PolyKinds, ExistentialQuantification, DataKinds, TypeOperators, TypeFamilies, GADTs #-} 

import Data.Functor.Identity 

type family (xs :: [*]) :-> (r :: *) :: * where 
  '[] :-> r = r 
  (x ': xs) :-> r = x -> (xs :-> r)

この型ファミリは n 項関数を表します。定義は非常に明白だと思います。

infixr 5 :>
data Prod (f :: k -> *) (xs :: [k]) where 
  Nil :: Prod f '[] 
  (:>) :: f x -> Prod f xs -> Prod f (x ': xs)

このデータ型は、型のリストにインデックスが付けられたベクトルです。これはあまり明白ではありません。Node何らかの形で型変数のリストを保存する必要がありますが、各型変数がNodeそれに適用されている必要があります。この定式化により、次のように簡単になります。

data Node a 
  = forall vs . CalculationNode (vs :-> a) (Prod Node vs)
  | TerminalNode a

次に、いくつかのヘルパー関数:

appFn :: vs :-> a -> Prod Identity vs -> a 
appFn z Nil = z 
appFn f (x :> xs) = appFn (f $ runIdentity x) xs 

mapProd :: (forall x . f x -> g x) -> Prod f xs -> Prod g xs 
mapProd _ Nil = Nil 
mapProd f (x :> xs) = f x :> mapProd f xs

関数は以前とeval同じくらい単純です。

eval :: Node a -> a 
eval (TerminalNode a) = a 
eval (CalculationNode fs as) = appFn fs $ mapProd (Identity . eval) as

あなたの例で変わるのは、タプルをProdコンストラクターに置き換えることだけです:

seven = CalculationNode (\s i -> i + length s) (abcd :> three :> Nil)
于 2015-10-28T14:33:24.843 に答える