Как получить FRP из прямых ациклических графов?

Ответ 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 (заменяя каждый node добавлением) как

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

То же кодирование может быть создано программно из представления графика, пройдя график таким образом, что каждый node будет посещаться после всех его зависимостей.

Есть три оптимизации, которые вы можете пожелать, которые не могут быть реализованы для сети, закодированной, используя только Applicative. Общая стратегия заключается в кодировании проблемы с точки зрения Applicative и нескольких дополнительных классов, необходимых для оптимизации или дополнительных функций. Затем вы предоставляете один или несколько интерпретаторов, которые реализуют необходимые классы. Это позволяет отделить проблему от реализации, позволяя вам написать собственный интерпретатор или использовать существующую библиотеку, например reactive, reactive-banana, или mvc-updates. Я не собираюсь обсуждать, как писать эти интерпретаторы или адаптировать представленное здесь представление к конкретному интерпретатору. Я собираюсь обсудить общее представление программы, которое необходимо для того, чтобы интерпретатор мог использовать эти оптимизации. Все три библиотеки, с которыми я связан, могут избежать перекомпоновки значений и могут вместить следующие оптимизации.

Наблюдаемый общий доступ

В предыдущем примере промежуточный node eleven определяется только один раз, но используется в трех разных местах. Реализация Applicative не сможет увидеть через ссылочную прозрачность, чтобы увидеть, что эти три eleven все одинаковы. Вы можете предположить, что реализация использует некоторую магию IO, чтобы заглянуть через ссылочную прозрачность или определить сеть, чтобы реализация могла видеть, что вычисление повторно используется.

Ниже приведен класс Applicative Functor, где результат вычисления можно разделить и повторно использовать в нескольких вычислениях. Этот класс не определен в библиотеке в любом месте, о котором я знаю.

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 Сложение и вычитание могут выполняться в произвольных группировках и до сих пор достичь того же результата. Это позволяет нам достичь того же результата, когда мы вычитаем старое значение и добавим новое значение к общей сумме, даже если старое значение было добавлено где-то посередине добавлений.

Любая структура с этими свойствами, а также замыкание и идентификация - это абелева группа. Следующий словарь содержит достаточную информацию для базовой библиотеки для выполнения той же оптимизации

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

Это класс структур, которые могут содержать абелевы группы

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

Аналогичная оптимизация возможна для построения карт.

Порог и равенство

Другой типичной операцией в нейронных сетях является сравнение значения с порогом и определение ответа полностью на основе того, прошло ли значение порогового значения. Если обновление ввода не меняет, какая сторона порога имеет значение, ответ не изменяется. Если ответ не изменился, нет никаких причин для пересчета всех нижележащих узлов. Возможность обнаруживать, что не было изменения порога Bool, или ответ равен равенству. Ниже приведен класс структур, которые могут использовать равенство. stabilize предоставляет экземпляр Eq для базовой структуры.

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