用Haskell表示计算图

 正如Will Ness的评论所指出的，AD的正确抽象是一个类别，而不是一个图。不幸的是，标准的Category类并没有真正做到这一点，因为它需要任何Haskell类型之间的箭头，但微分只在光滑流形之间有意义。大多数库不知道流形，并将其进一步限制在欧几里得向量空间(他们将其表示为"向量"或"张量"，它们只是数组(。确实没有一个令人信服的理由是具有限制性——任何仿射空间都适用于前向模式AD；对于反向模式，您还需要差向量的对偶空间的概念。

data FwAD x y = FwAD (x -> (y, Diff x -> Diff y))
data RvAD x y = RvAD (x -> (y, DualVector (Diff y) -> DualVector (Diff x)))

其中CCD_ 2函数必须是线性函数。(你可以为这样的函数使用专用的箭头类型，也可以只使用恰好是线性的(->)函数。(在反向模式中唯一不同的是，表示这个线性映射的伴随，而不是映射本身。(在实值矩阵实现中，线性映射是雅可比矩阵，伴随版本是它的转置，但不使用矩阵，它们在这方面效率非常低。(
整洁，对吧？人们一直在谈论的那些图/遍历/突变/向后传递的废话其实并不需要。(详见Conal的论文。(

因此，要使这在Haskell中有用，您需要实现类别组合子。这几乎正是我编写受限类别包的目的。以下是您所需的概要实例化：

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
...

这些实例都很简单，几乎没有歧义，让编译器消息来指导您(类型化的孔_非常有用(。基本上，只要需要范围内类型的变量，就使用它；当需要范围中而非的向量空间类型的变量时，请使用zeroV。

到那时，您将真正拥有所有基本的可微函数工具，但要真正定义这些函数，您需要使用带有大量.、&&&和***组合子和硬编码数字基元的无点样式，这看起来很不传统，也很令人困惑。为了避免这种情况，您可以使用代理值：这些值基本上假装是简单的数字变量，但实际上包含来自某个固定域类型的整个类别箭头。(这基本上就是练习的"构建图"部分。(您可以简单地使用所提供的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箭头的组合，&&&"拆分"数据流，***并行组合，即即使输入和最终结果是简单的Double，中间结果也将通过合适的元组类型提取。[我想，这就是你标题问题的答案：有向图在某种意义上被表示为一个分支组成链，原则上与你在Arrows的图表解释中发现的相同。]