haskell - 如何从有向无环图导出 FRP？

Question

我目前正在研究我的下一个项目。这是在一个预先规划阶段，所以这个问题只是为了了解现有技术。

设置

我有一个具有多个输入和输出的有向无环图 (DAG)，现在考虑人工神经元网络:



处理这种结构的常用方法是在每个(时间)步长上处理整个网络。相信是 netwire 等frp库使用的方法.

现在我处于幸运的位置，我有一个事件流，每个事件都代表输入节点之一的变化。这个想法是，如果我可以静态地知道给定的更改只会影响其中的一部分，我可能不必遍历网络中的每个节点。

示例

在上图中，5、7 和 3 是输入，11 和 8 是“隐藏”节点，2、9 和 10 是输出节点。节点 5 处的更改只会影响节点 11，实际上会影响节点 2、9 和 10。我不需要处理节点 7、3 和 8。

目标

以尽可能少的延迟处理此类网络。图的大小可能会达到 10 万个节点，每个节点进行适度的计算。

计划

我希望有人站出来宣传刚刚完成工作的图书馆 X。

否则，我目前的计划是从图形描述中导出每个输入节点的计算。可能我会用 Par monad，这样我就不必自己处理数据依赖性，并且仍然可以从多核机器中受益。

问题

是否有任何图书馆可以满足我的需求？

是我的 Par计划可行吗？这在多大程度上取决于每个节点所需的处理量？

Answer 1

像这样的问题通常针对 Applicative 进行编码。或 Arrow抽象。我只讨论Applicative . Applicative类型类，在 Control.Applicative 中找到, 允许通过 pure 提供值和函数和应用于值的函数 <*> .

class Functor f => Applicative f where
    -- | Lift a value.
    pure :: a -> f a

    -- | Sequential application.
    (<*>) :: f (a -> b) -> f a -> f b

您的示例图可以非常简单地编码为 Applicative (用加法替换每个节点)作为

example1 :: (Applicative f, Num a) => f a -> f a -> f a -> f (a, a, a)
example1 five seven three = 
    let
        eleven = pure (+) <*> five   <*> seven
        eight  = pure (+) <*> seven  <*> three
        two    = pure id  <*> eleven
        nine   = pure (+) <*> eleven <*> eight
        ten    = pure (+) <*> eleven <*> three
    in
        pure (,,) <*> two <*> nine <*> ten

可以通过遍历图从图的表示以编程方式创建相同的编码，这样每个节点都将在其所有依赖项之后被访问。

对于仅使用 Applicative 编码的网络，您可能希望无法实现三种优化。 .一般策略是根据 Applicative 对问题进行编码。以及优化或额外功能所需的一些额外类。然后提供一个或多个实现必要类的解释器。这使您可以将问题与实现分开，允许您编写自己的解释器或使用现有的库，如 reactive , reactive-banana , 或 mvc-updates .我不打算讨论如何编写这些解释器或将这里给出的表示调整到特定的解释器。我将只讨论为了让底层解释器能够利用这些优化而需要的程序的通用表示。我链接的所有三个库都可以避免重新计算值，并且可以进行以下优化。

可观察分享

在前面的例子中，中间节点 eleven只定义一次，但在三个不同的地方使用。 Applicative 的实现将无法通过参照透明看到这三个 eleven s 都是一样的。您可以假设该实现使用了一些 IO magic to peek through referential transparency或者定义网络，以便实现可以看到正在重用计算。

以下是 Applicative的类 Functor s 其中一个计算的结果可以被分割并在多个计算中重用。这个类没有在我知道的任何地方的库中定义。

class Applicative f => Divisible f where
    (</>) :: f a -> (f a -> f b) -> f b

infixl 2 </>

您的示例可以非常简单地编码为 Divisible Functor作为

example2 :: (Divisible f, Num a) => f a -> f a -> f a -> f (a, a, a)
example2 five seven three = 
    pure (+) <*> five   <*> seven </> \eleven ->
    pure (+) <*> seven  <*> three </> \eight  ->
    pure id  <*> eleven           </> \two    ->
    pure (+) <*> eleven <*> eight </> \nine   ->
    pure (+) <*> eleven <*> three </> \ten    ->
    pure (,,) <*> two <*> nine <*> ten

和和阿贝尔群

典型的神经元计算其输入的加权总和，并将响应函数应用于该总和。对于度数较大的神经元，将其所有输入相加是非常耗时的。更新总和的一个简单优化是减去旧值并添加新值。这利用了加法的三个性质:

反 - a * b * b⁻¹ = a减法是加一个数的倒数，这个倒数允许我们从总数中删除先前添加的数

交换性 - a * b = b * a无论执行顺序如何，加法和减法都会得到相同的结果。这让我们在减去旧值并将新值添加到总数中时，即使旧值不是最近添加的值也能达到相同的结果.

结合性 - a * (b * c) = (a * b) * c可以在任意分组中执行加法和减法，并且仍然达到相同的结果。这让我们在减去旧值并将新值添加到总数时得到相同的结果，即使旧值是在加法中间的某个地方添加的。

任何具有这些属性以及闭包和身份的结构都是 Abelian group .以下字典包含足够的信息供底层库执行相同的优化

data Abelian a = Abelian {
    id  :: a,
    inv :: a -> a,
    op  :: a -> a -> a
}

这是可以对阿贝尔群求和的结构类

class Total f where 
    total :: Abelian a -> [f a] -> f a

类似的优化可以用于 map 的构建。

阈值和平等

神经网络中的另一个典型操作是将一个值与一个阈值进行比较，并完全根据该值是否超过阈值来确定响应。如果对输入的更新没有改变值落在阈值的哪一侧，则响应不会改变。如果响应没有改变，就没有理由重新计算所有下游节点。检测阈值没有变化的能力 Bool或者回应是平等的。以下是可以利用平等的结构类别。 stabilize提供 Eq实例到底层结构。

class Stabilizes f where
    stabilize :: Eq a => f a -> f a