Оценка строго типизированного графика вычислений с произвольным числом зависимостей на узел

Question

Я хотел бы оценить простой граф вычислений. Я был в состоянии написать код, чтобы сделать это для вычисления графа, где каждый нетерминал узел имеет два зависимостей (и это может быть тривиально распространено на любое фиксированное число зависимостей)

{-# 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 колдовство, но я даже не знаю, с чего начать. Решения и подсказки приветствуются.

Answer 1

Конечно, с немного «колдовства» это обобщает довольно красиво:

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

import Data.Functor.Identity 

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

Этот тип семьи представляет собой п-арные функции. Полагаю, это определение совершенно очевидно.

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) 

Answer 2

Воспользуйтесь подсказкой от Haskell и дайте все только одну зависимость. Таким образом:

{-# LANGUAGE ExistentialQuantification #-} 

module Graph where 

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

eval :: Node a -> a 
eval (CalculationNode f dep) = (eval f) (eval dep) 
eval (TerminalNode a) = a 

three :: Node Int 
three = TerminalNode 3 

abcd :: Node String 
abcd = TerminalNode "abcd" 

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

Не нужно колдовство! Возможно, вы захотите сделать короткую инфиксную версию CalculationNode, чтобы сделать некоторые вещи более читабельными; например

infixl 0 $$ 
($$) = CalculationNode 

seven' = TerminalNode (\s i -> i + length s) $$ abcd $$ three