在 Haskell 中表示计算图
Representing a computational graph in Haskell
我正在尝试在Haskell中编写一个简单的自动微分包。
在 Haskell 中表示类型安全（有向）计算图的有效方法是什么？我知道 ad 包为此使用“data-reify”方法，但我不太熟悉它。谁能给我一些见解？谢谢！
正如 Will Ness 的评论所指出的，AD 的正确抽象是类别，而不是图形。不幸的是，标准 Category class doesn't really do the trick, because it requires arrows between any Haskell types, but differentiation only makes sense between smooth manifolds. Most libraries don't know about manifolds and restrict it further to Euclidean vector spaces (which they represent as “vectors” or “tensors” which are just arrays). There really isn't a compelling reason to be that restrictive – any affine space 将适用于 forward-mode AD；对于反向模式，您还需要双 space 到差分向量的概念。
data FwAD x y = FwAD (x -> (y, Diff x -> Diff y))
data RvAD x y = RvAD (x -> (y, DualVector (Diff y) -> DualVector (Diff x)))
其中 Diff x -> Diff y 函数必须是 linear function. (You can use a dedicated arrow type for such functions, or you can just use (->) functions which happen to be linear.) The only thing that's different in reverse-mode is that the adjoint of this linear map is represented, instead of the map itself. (In a real-valued matrix implementation, the linear mapping is the Jacobian matrix 并且伴随版本是它的转置，但是 不要 使用矩阵，它们非常低效为了这。）
很好，对吧？人们一直在谈论的所有 graph/traversal/mutation/backwards-pass 废话并不是真的需要。 （详见 Conal's paper。）
因此，要使其在 Haskell 中有用，您需要实施类别组合器。这几乎正是我写 constrained-categories package 的目的。这是您需要的大纲实例化：
import qualified Prelude as Hask
import Control.Category.Constrained.Prelude
import Control.Arrow.Constrained
import Data.AffineSpace
import Data.AdditiveGroup
import Data.VectorSpace
instance Category FwAD where
type Object FwAD a
= (AffineSpace a, VectorSpace (Diff a), Scalar (Diff a) ~ Double)
id = FwAD $ \x -> (x, id)
FwAD f . FwAD g = FwAD $ \x -> case g x of
(gx, dg) -> case f gx of
(fgx, df) -> (fgx, df . dg)
instance Cartesian FwAD where
...
instance Morphism FwAD where
...
instance PreArrow FwAD where
...
instance WellPointed FwAD where
...
这些实例都很简单，几乎没有歧义，让编译器消息指导您（打字孔 _ 非常有用）。基本上，只要需要范围内类型的变量，就使用它；当需要范围内 不是 的 vector-space 类型的变量时，请使用 zeroV.
到那时，您将真正拥有所有基本的 可微函数 工具，但要实际定义此类函数，您需要使用 point-free 样式许多 .、&&& 和 *** 组合器和 hard-coded 数字原语，看起来非常规且相当混乱。为避免这种情况，您可以使用 agent values: values that basically pretend to be simple number variables, but actually contain an entire category arrow from some fixed domain type. (This would basically be the “building up a graph” part of the exercise.) You can simply use the provided GenericAgent 包装器。
instance HasAgent FwAD where
type AgentVal FwAD a v = GenericAgent FwAD a v
alg = genericAlg
($~) = genericAgentMap
instance CartesianAgent FwAD where
alg1to2 = genericAlg1to2
alg2to1 = genericAlg2to1
alg2to2 = genericAlg2to2
instance PointAgent (GenericAgent FwAD) FwAD a x where
point = genericPoint
instance ( Num v, AffineSpace v, Diff v ~ v, VectorSpace v, Scalar v ~ v
, Scalar a ~ v )
=> Num (GenericAgent FwAD a v) where
fromInteger = point . fromInteger
(+) = genericAgentCombine . FwAD $ \(x,y) -> (x+y, \(dx,dy) -> dx+dy)
(*) = genericAgentCombine . FwAD $ \(x,y) -> (x*y, \(dx,dy) -> y*dx+x*dy)
abs = genericAgentMap . FwAD $ \x -> (abs x, \dx -> if x<0 then -dx else dx)
...
instance ( Fractional v, AffineSpace v, Diff v ~ v, VectorSpace v, Scalar v ~ v
, Scalar a ~ v )
=> Fractional (GenericAgent FwAD a v) where
...
instance (...) => Floating (...) where
...
如果您已经完成了所有这些实例，也许还有一个简单的助手来提取结果
evalWithGrad :: FwAD Double Double -> Double -> (Double, Double)
evalWithGrad (FwAD f) x = case f x of
(fx, df) -> (fx, df 1)
那么你可以写这样的代码
> evalWithGrad (alg (\x -> x^2 + x) 3)
(12.0, 7.0)
> evalWithGrad (alg sin 0)
(0.0, 1.0)
在幕后，这些代数表达式构成了 FwAD 个箭头与 &&& “splitting” the data flow and *** composing in parallel, i.e. even if the input and final result are simple Double then the intermediate results will be pulled through a suitable tuple type. [That would, I guess, be the answer to your title question: the directed graph is in a sense represented as a branched composition chain, in principle the same thing as you find in those diagram explanations of Arrows 的组合。]
我正在尝试在Haskell中编写一个简单的自动微分包。
在 Haskell 中表示类型安全（有向）计算图的有效方法是什么？我知道 ad 包为此使用“data-reify”方法，但我不太熟悉它。谁能给我一些见解？谢谢！
正如 Will Ness 的评论所指出的，AD 的正确抽象是类别，而不是图形。不幸的是，标准 Category class doesn't really do the trick, because it requires arrows between any Haskell types, but differentiation only makes sense between smooth manifolds. Most libraries don't know about manifolds and restrict it further to Euclidean vector spaces (which they represent as “vectors” or “tensors” which are just arrays). There really isn't a compelling reason to be that restrictive – any affine space 将适用于 forward-mode AD；对于反向模式，您还需要双 space 到差分向量的概念。
data FwAD x y = FwAD (x -> (y, Diff x -> Diff y))
data RvAD x y = RvAD (x -> (y, DualVector (Diff y) -> DualVector (Diff x)))
其中 Diff x -> Diff y 函数必须是 linear function. (You can use a dedicated arrow type for such functions, or you can just use (->) functions which happen to be linear.) The only thing that's different in reverse-mode is that the adjoint of this linear map is represented, instead of the map itself. (In a real-valued matrix implementation, the linear mapping is the Jacobian matrix 并且伴随版本是它的转置，但是 不要 使用矩阵，它们非常低效为了这。）
很好，对吧？人们一直在谈论的所有 graph/traversal/mutation/backwards-pass 废话并不是真的需要。 （详见 Conal's paper。）
因此，要使其在 Haskell 中有用，您需要实施类别组合器。这几乎正是我写 constrained-categories package 的目的。这是您需要的大纲实例化：
import qualified Prelude as Hask
import Control.Category.Constrained.Prelude
import Control.Arrow.Constrained
import Data.AffineSpace
import Data.AdditiveGroup
import Data.VectorSpace
instance Category FwAD where
type Object FwAD a
= (AffineSpace a, VectorSpace (Diff a), Scalar (Diff a) ~ Double)
id = FwAD $ \x -> (x, id)
FwAD f . FwAD g = FwAD $ \x -> case g x of
(gx, dg) -> case f gx of
(fgx, df) -> (fgx, df . dg)
instance Cartesian FwAD where
...
instance Morphism FwAD where
...
instance PreArrow FwAD where
...
instance WellPointed FwAD where
...
这些实例都很简单，几乎没有歧义，让编译器消息指导您（打字孔 _ 非常有用）。基本上，只要需要范围内类型的变量，就使用它；当需要范围内 不是 的 vector-space 类型的变量时，请使用 zeroV.
到那时，您将真正拥有所有基本的 可微函数 工具，但要实际定义此类函数，您需要使用 point-free 样式许多 .、&&& 和 *** 组合器和 hard-coded 数字原语，看起来非常规且相当混乱。为避免这种情况，您可以使用 agent values: values that basically pretend to be simple number variables, but actually contain an entire category arrow from some fixed domain type. (This would basically be the “building up a graph” part of the exercise.) You can simply use the provided GenericAgent 包装器。
instance HasAgent FwAD where
type AgentVal FwAD a v = GenericAgent FwAD a v
alg = genericAlg
($~) = genericAgentMap
instance CartesianAgent FwAD where
alg1to2 = genericAlg1to2
alg2to1 = genericAlg2to1
alg2to2 = genericAlg2to2
instance PointAgent (GenericAgent FwAD) FwAD a x where
point = genericPoint
instance ( Num v, AffineSpace v, Diff v ~ v, VectorSpace v, Scalar v ~ v
, Scalar a ~ v )
=> Num (GenericAgent FwAD a v) where
fromInteger = point . fromInteger
(+) = genericAgentCombine . FwAD $ \(x,y) -> (x+y, \(dx,dy) -> dx+dy)
(*) = genericAgentCombine . FwAD $ \(x,y) -> (x*y, \(dx,dy) -> y*dx+x*dy)
abs = genericAgentMap . FwAD $ \x -> (abs x, \dx -> if x<0 then -dx else dx)
...
instance ( Fractional v, AffineSpace v, Diff v ~ v, VectorSpace v, Scalar v ~ v
, Scalar a ~ v )
=> Fractional (GenericAgent FwAD a v) where
...
instance (...) => Floating (...) where
...
如果您已经完成了所有这些实例，也许还有一个简单的助手来提取结果
evalWithGrad :: FwAD Double Double -> Double -> (Double, Double)
evalWithGrad (FwAD f) x = case f x of
(fx, df) -> (fx, df 1)
那么你可以写这样的代码
> evalWithGrad (alg (\x -> x^2 + x) 3)
(12.0, 7.0)
> evalWithGrad (alg sin 0)
(0.0, 1.0)
在幕后，这些代数表达式构成了 FwAD 个箭头与 &&& “splitting” the data flow and *** composing in parallel, i.e. even if the input and final result are simple Double then the intermediate results will be pulled through a suitable tuple type. [That would, I guess, be the answer to your title question: the directed graph is in a sense represented as a branched composition chain, in principle the same thing as you find in those diagram explanations of Arrows 的组合。]