3

我想评估一个简单的计算图。我能够为计算图编写代码，其中每个非终端节点都有两个依赖项（这可以很容易地扩展到任何固定数量的依赖项）

{-# 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 回答
0

从 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
于 2015-10-28T21:03:14.637 回答