L01*_*man 9 haskell expression
比方说我有:
f :: Double -> Double
f x = 3*x^2 + 5*x + 9
我想计算这个函数的衍生物并写
derivate f
以便
derivate f == \x -> 6*x + 5
但如何定义derivate？
derivate :: (a -> a) -> (a -> a)
derivate f = f' -- how to compute f'?
我知道没有本地方法可以做到这一点,但是有一个库可以吗？
我们是否必须依靠"meta"-datatypes来实现这一目标？
data Computation = Add Exp Expr | Mult Expr Expr | Power Expr Expr -- etc
那么,为每个函数创建一个相应的构造函数是不是很痛苦？但是,数据类型不应表示函数(解析器除外).
是纯粹的,因为它的长期重写功能的一个很好的选择？它有它的缺点吗？
列表价格合理吗？
f :: [Double]
f = [3, 5, 9]
derivate :: (a -> [a])
derivate f = (*) <$> f <*> (getNs f)
compute f x = sum $
((*) . (^) x) <$> (getNs f) <*> f
getNs f = (reverse (iterate (length f) [0..]))
Haskell现在看起来它依赖于LISP的语法不太合适.等待一起使用的函数和参数完全存储在数据类型中.而且,它不是很自然.
它们似乎不够灵活,不能用于derivate多项式以外的函数,例如单应函数.
例如,现在,我想在游戏中使用衍生品.角色在使用功能制作的地板上运行,如果地板足够陡峭,我希望他能够滑动.
我还需要为各种目的求解方程.一些例子:
我是一艘宇宙飞船,我想小睡一下.在我睡觉的时候,如果我没有小心翼翼地放置自己,我可能会因为引力而在地球上坠毁.我没有足够的气体远离天体,我也没有地图.因此,我必须把自己置于这个区域内的物体之间,以便取消它们对我的重力影响的总和.
x和y是我的坐标.gravity是一个函数,它接受两个对象并返回它们之间的重力矢量.如果有两个物体,比如说地球和月亮,除了我之外,我需要做的就是找到要去的地方:
gravity earth spaceship + gravity moon spaceship == (0, 0)
它比从头开始创建新功能更简单,更快捷等等equigravityPoint :: Object -> Object -> Object -> Point.
如果除了我之外还有3个物体,它仍然很简单.
gravity earth spaceship + gravity moon spaceship + gravity sun spaceship == (0, 0)
4和n相同.处理对象列表比使用这种方式简单得多equigravityPoint.
其他例子.我想编写一个射击我的敌人机器人.如果他只是针对我现在的位置射击,如果我向我跑去,他会得到我,但是如果我跳起来摔倒在他身上,他会想念我的.一个更智能的机器人就是这样想的:"好吧,他从墙上跳下来.如果我射击目标他现在的子弹将不会得到他,因为他将移动到那时.所以我会预料到他会在哪里在几秒钟内拍摄,以便子弹和他同时到达这一点".基本上,我需要能够计算轨迹.例如,对于这种情况,我需要解决方案trajectoryBullet == trajectoryCharacter,它给出了线和抛物线相交的点.
一个类似且简单的例子,不涉及速度.我是一个消防员机器人,还有一座建筑物着火了.另一队消防员正在用水枪对抗火灾.我和有人跳了起来.当我的朋友们开水时,我拿着蹦床.我需要去人们将要去的地方.所以我需要轨迹和方程求解.
Ant*_*sky 29
这样做的一种方法是自动区分而不是象征性区分; 这是一种在一次计算中同时计算f(x)和f '(x)的方法.使用双数字这是一种非常酷的方式,我从Dan"sigfpe"Piponi关于自动差异化的优秀博客文章中了解到这一点.你可能应该去读一下,但这是基本的想法.相反,与实数(或工作中Double,我们最喜欢的(？)他们的传真),您可以定义一组新的,我会打电话到d,通过相邻的一个新元素ε到ℝ使得ε 2 = 0.这很像我们通过将新元素i连接到define 使得i 2 = -1 来定义复数way的方式.(如果你喜欢代数,这是相同的话说d =ℝ[X] /⟨x 2 ⟩.)因此,d的每一个元件的形式为一个 + bε,其中一个和b是真实的.对双数字的算术可以像您期望的那样工作:
(由于ε 2 = 0,划分比较复杂,虽然乘由这招结合您的复数仍然有效使用;参见维基百科的解释.更多)
现在,为什么这些有用？直觉上,ε的作用类似于无穷小,允许您用它来计算导数.实际上,如果我们使用不同的名称重写乘法规则,它就会变成
并且ε的系数看起来很像区分功能产品的产品规则!
那么,让我们弄清楚一大类函数会发生什么.由于我们忽略了上面的除法,假设我们有一些函数f:ℝ→ℝ由幂级数定义(可能是有限的,所以任何多项式都可以,像sin(x),cos(x)和e x这样的东西)).然后我们可以用明显的方式定义一个新的函数f D:D→D:我们不是添加实数,而是添加双数等等.然后我声称f D(x + ε)= f(x) + f '(x)ε.首先,我们可以通过归纳表明,对于任何自然数i,情况是(x + ε)i = x i + ix i - 1ε ; 这将建立f(x)= x k的情况下的导数结果.在基本情况下,当i = 0 时,这种平等显然成立.然后假设它适用于i,我们有
事实上,这就是我们想要的.现在,考虑到我们的动力系列f,我们知道这一点
然后我们有
大!所以双重数字(至少在这种情况下,但结果通常是真的)可以为我们做区分.我们所要做的就是将原始函数应用于实数x,而不是双数x + ε,然后提取得到的ε系数.我打赌你可以看到如何在Haskell中实现这一点:
data Dual a = !a :+? !a deriving (Eq, Read, Show)
infix 6 :+?
instance Num a => Num (Dual a) where
(a :+? b) + (c :+? d) = (a+c) :+? (b+d)
(a :+? b) - (c :+? d) = (a-c) :+? (b-d)
(a :+? b) * (c :+? d) = (a*c) :+? (b*c + a*d)
negate (a :+? b) = (-a) :+? (-b)
fromInteger n = fromInteger n :+? 0
-- abs and signum might actually exist, but I'm not sure what they are.
abs _ = error "No abs for dual numbers."
signum _ = error "No signum for dual numbers."
-- Instances for Fractional, Floating, etc., are all possible too.
differentiate :: Num a => (Dual a -> Dual a) -> (a -> a)
differentiate f x = case f (x :+? 1) of _ :+? f'x -> f'x
-- Your original f, but with a more general type signature. This polymorphism is
-- essential! Otherwise, we can't pass f to differentiate.
f :: Num a => a -> a
f x = 3*x^2 + 5*x + 9
f' :: Num a => a -> a
f' = differentiate f
然后,瞧瞧:
*Main> f 42
5511
*Main> f' 42
257
其中,作为Wolfram Alpha的可以确认,是完全正确的答案.
有关这些东西的更多信息绝对可用.我不是这方面的专家; 我只是觉得这个想法真的很酷,所以我抓住这个机会鹦鹉学习我读过的东西并制定了一两个简单的证明.Dan Piponi写了更多关于双数/自动微分的文章,其中包括一个帖子,其中,他展示了一个允许偏导数的更一般的结构.Conal Elliott有一篇文章,他以一种类似的方式展示了如何计算导数塔(f(x),f '(x),f "(x),......).以上链接的关于自动差异的维基百科文章更详细,包括其他一些方法.(这显然是"前进模式自动区分"的一种形式,但"反向模式"也存在,并且显然可以更快.)
最后,有一个关于自动差异化的Haskell wiki页面,它链接到一些文章 - 更重要的是,一些Hackage包!我从来没有使用过这些,但似乎Edward Kmett 的ad软件包是最完整的,处理多种不同的自动差异化方法 - 事实证明他在编写软件包之后上传了该软件包以正确回答另一个Stack Overflow问题.
我确实想补充一点.你说"但是,数据类型不应该代表函数(解析器除外)." 我不得不在那里不同意 - 将你的函数转换为数据类型对于这种情况下的各种事情都是很好的.(无论如何,是什么让解析器变得特别？)每当你有一个你想要内省的函数时,将它作为一种数据类型进行重新定义可能是一个很好的选择.例如,这里是符号微分的编码,就像上面的自动微分编码一样:
data Symbolic a = Const a
| Var String
| Symbolic a :+: Symbolic a
| Symbolic a :-: Symbolic a
| Symbolic a :*: Symbolic a
deriving (Eq, Read, Show)
infixl 6 :+:
infixl 6 :-:
infixl 7 :*:
eval :: Num a => (String -> a) -> Symbolic a -> a
eval env = go
where go (Const a) = a
go (Var x) = env x
go (e :+: f) = go e + go f
go (e :-: f) = go e - go f
go (e :*: f) = go e * go f
instance Num a => Num (Symbolic a) where
(+) = (:+:)
(-) = (:-:)
(*) = (:*:)
negate = (0 -)
fromInteger = Const . fromInteger
-- Ignoring abs and signum again
abs = error "No abs for symbolic numbers."
signum = error "No signum for symbolic numbers."
-- Instances for Fractional, Floating, etc., are all possible too.
differentiate :: Num a => Symbolic a -> String -> Symbolic a
differentiate f x = go f
where go (Const a) = 0
go (Var y) | x == y = 1
| otherwise = 0
go (e :+: f) = go e + go f
go (e :-: f) = go e - go f
go (e :*: f) = go e * f + e * go f
f :: Num a => a -> a
f x = 3*x^2 + 5*x + 9
f' :: Num a => a -> a
f' x = eval (const x) $ differentiate (f $ Var "x") "x"
再一次:
*Main> f 42
5511
*Main> f' 42
257
这两种解决方案(或者说它的一部分)的美妙之处在于,只要您的原始版本f具有多态性(类型Num a => a -> a或类似),您就不必修改f!您需要将衍生相关代码放在新数据类型和差异函数的定义中; 您可以免费获得现有功能的衍生产品.