Схема рекурсии для символьного дифференцирования

Следуя терминологии из этой замечательной серии, давайте представим такое выражение, как (1 + x^2 - 3x)^3 на Term Expr, где типы данных следующие:

data Expr a =
    Var
  | Const Int
  | Plus a a
  | Mul a a
  | Pow a Int
  deriving (Functor, Show, Eq)

data Term f = In { out :: f (Term f) }

Существует ли схема рекурсии, подходящая для выполнения символьного дифференцирования? Я чувствую, что это почти футуморфизм, специализирующийся на Term Expr, то есть futu deriveFutu для соответствующей функции deriveFutu:

data CoAttr f a  
  = Automatic a
  | Manual (f (CoAttr f a))

futu :: Functor f => (a -> f (CoAttr f a)) -> a -> Term f  
futu f = In <<< fmap worker <<< f where  
    worker (Automatic a) = futu f a
    worker (Manual g) = In (fmap worker g)

Это выглядит довольно хорошо, за исключением того, что подчеркнутые переменные — это Terms вместо CoAttrs:

deriveFutu :: Term Expr -> Expr (CoAttr Expr (Term Expr))
deriveFutu (In (Var))      = (Const 1)
deriveFutu (In (Const _))  = (Const 0)
deriveFutu (In (Plus x y)) = (Plus (Automatic x) (Automatic y))
deriveFutu (In (Mul x y))  = (Plus (Manual (Mul (Automatic x) (Manual _y)))
                                   (Manual (Mul (Manual _x) (Automatic y)))
                             )
deriveFutu (In (Pow x c))  = (Mul (Manual (Const c)) (Manual (Mul (Manual (Pow _x (c-1))) (Automatic x))))

Вариант без рекурсивных схем выглядит так:

derive :: Term Expr -> Term Expr
derive (In (Var))      = In (Const 1)
derive (In (Const _))  = In (Const 0)
derive (In (Plus x y)) = In (Plus (derive x) (derive y))
derive (In (Mul x y))  = In (Plus (In (Mul (derive x) y)) (In (Mul x (derive y))))
derive (In (Pow x c))  = In (Mul (In (Const c)) (In (Mul (In (Pow x (c-1))) (derive x))))

В дополнение к этому вопросу, существует ли схема рекурсии для дифференциации и устранения «пустых» Expr, таких как Plus (Const 0) x, которые возникают в результате дифференциации - за один проход по данным?


haskell recursion-schemes
person nnnmmm    schedule 22.05.2018    source источник
comment
Значит, ваши выражения всегда имеют одну переменную?   -  person Willem Van Onsem    schedule 22.05.2018
comment
Максимум один, да, если я правильно понял ваш вопрос.   -  person nnnmmm    schedule 22.05.2018

Ответы (1)


arrow_upward
5
arrow_downward

Посмотрите на правило дифференциации для продукта:

(u v)' = u' v + v' u

Что нужно знать, чтобы выделить продукт? Вам необходимо знать производные подтерминов (u', v'), а также их значения (u, v).

Это именно то, что дает вам параморфизм.

para
  :: Functor f
  => (f (b, Term f) -> b)
  -> Term f -> b
para g (In a) = g $ (para g &&& id) <$> a

derivePara :: Term Expr -> Term Expr
derivePara = para $ In . \case
  Var -> Const 1
  Const _ -> Const 0
  Plus x y -> Plus (fst x) (fst y)
  Mul x y -> Plus
    (In $ Mul (fst x) (snd y))
    (In $ Mul (snd x) (fst y))
  Pow x c -> Mul
    (In (Const c))
    (In (Mul
      (In (Pow (snd x) (c-1)))
      (fst x)))

Внутри параморфизма fst дает вам доступ к производной подтермина, а snd дает вам сам термин.

В дополнение к этому вопросу, существует ли схема рекурсии для дифференциации и устранения «пустых» выражений, таких как Plus (Const 0)x, которые возникают в результате дифференциации - за один проход по данным?

Да, это все еще параморфизм. Самый простой способ убедиться в этом — использовать интеллектуальные конструкторы, такие как

plus :: Term Expr -> Term Expr -> Expr (Term Expr)
plus (In (Const 0)) (In x) = x
plus (In x) (In (Const 0)) = x
plus x y = Plus x y

и использовать их при определении алгебры. Вероятно, вы могли бы выразить это как своего рода слияние пара-ката.

person Roman Cheplyaka    schedule 22.05.2018
comment
Ага. Я пришел к такому же выводу, но затем потратил время, пытаясь найти способ (в пределах recursion-schemes) избавиться от In на RHS. Если и есть способ, то я его не нашел. - person dfeuer; 22.05.2018
comment
Я думаю, что вы переворачиваете пару по сравнению с recursion-schemes, что может быть не лучшим вариантом. Я также думаю, что было бы лучше явно сопоставить пары с образцом, с x и dx в любом порядке. - person dfeuer; 22.05.2018
comment
Я думаю, что у этого все еще есть ошибка, он возвращает 3 * (1 + x²-3x)² * (1 + x²-3x) для ввода (1 + x²-3x)³ -- изменить: Неважно, я использовал para из связанный ряд, аргументы которого перевернуты. - person nnnmmm; 22.05.2018