代码之家 › 专栏 › 技术社区 › nnnmmm kennytm

符号微分的递归方案

recursion-schemes haskell

2

nnnmmm kennytm · 技术社区 · 7 年前

以下术语来自 this excellent series ,让我们表示一个表达式,例如 (1 + x^2 - 3x)^3 由A 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) }

是否有适合执行符号微分的递归方案?我觉得这几乎是一种未来主义 术语表达式 ,即 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)

除了下划线变量 Term S而不是 CoAttr S:

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 这是差异化的结果——一次传递数据?

1 回复 | 直到 7 年前

1

5

Roman Cheplyaka 7 年前

查看产品的差异化规则:

(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

在定义代数时使用它们。你也可以把它表示为某种准卡塔融合。