haskell - 符号微分的递归方案
问题描述
按照这个优秀系列中的术语,让我们表示一个表达式,例如(1 + x^2 - 3x)^3
by 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) }
是否有适合执行符号微分的递归方案?我觉得它几乎是专门用于 的 Futumorphism 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)
这看起来很不错,只是下划线的变量是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
差异而出现的“空”——一次遍历数据?
解决方案
查看产品的差异化规则:
(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
为您提供项本身。
作为对这个问题的扩展,是否存在一种递归方案来区分和消除由于微分而产生的“空”Expr(例如
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
并在定义代数时使用它们。您也可以将其表达为某种准催化融合。
推荐阅读
- r - 在不打开/保存的情况下评估 Excel 文件
- c - 在 C 中使用 execlp 调用可执行文件
- netlify-cms - Netlify CMS 离线本地主机
- google-sheets - 用于将数据更新到多个工作表的 Google 表格、表格和查询?
- java - PowerMockito VerifyStatic 在 2.0.0-beta5 中不起作用
- android - 如何使用 CMake 在 Android Studio 3.2 中创建静态库(.a 文件)
- python - python 3 - getpass.getpass() 正在回显密码......似乎没有任何效果
- git - Git - 在 Windows 上克隆本地存储库
- javascript - 将 Json 对象转换为 html
- angular - 如何在 Angular 中转换 ControlValueAccessor 的值?