haskell - 如何处理 Haskell 中的表达式？

Question

假设我有:

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'?

我知道没有本地方法可以做到这一点，但是有一个图书馆可以吗？

我们是否必须依靠“元”数据类型来实现这一目标？

data Computation = Add Exp Expr | Mult Expr Expr | Power Expr Expr -- etc

那么，为每个函数做一个对应的构造函数是不是很痛苦？但是，数据类型不应表示函数(解析器除外)。

是 Pure一个很好的选择，因为它的术语重写功能？它不也有它的缺点吗？

list 是否负担得起？

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多项式以外的函数，例如单应函数。

例如，现在我想在游戏中使用衍生品。角色在使用函数制作的地板上奔跑，如果地板足够陡峭，我希望他能滑动。

我还需要为各种目的求解方程。一些例子:

我是一艘宇宙飞船，我想小睡一会儿。在我 sleep 的时候，如果我不小心放置自己，我可能会因为重力而坠毁在一个星球上。我没有足够的气体远离天体，我也没有 map 。
所以我必须把自己放在这个区域的物体之间，这样它们对我的引力影响就被抵消了。 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 ，它给出了直线和抛物线相交的点。

一个不涉及速度的类似且更简单的示例。
我是一名消防员机器人，有一栋建筑物着火了。另一队消防员正在用水枪灭火。我是，还有人从 .当我的 friend 们在打水时，我拿着蹦床。
我需要先去人们会跌倒的地方。所以我需要轨迹和方程求解。

Answer 1

这样做的一种方法是做 automatic differentiation而不是象征性的分化；这是一种在一次计算中同时计算 f(x) 和 f'(x) 的方法。使用 dual numbers 有一种非常酷的方法可以做到这一点我从 Dan "sigfpe" Piponi's excellent blog post on automatic differentiation 了解到的.你可能应该去读一读，但这是基本的想法。不是使用实数(或 Double，我们最喜欢的(？)传真)，而是定义一个新集合，我将称其为 D，通过将新元素 ε 与 ℝ 邻接，使得 ε2 = 0. 这很像我们定义复数 ℂ 的方式，通过将新元素 i 连接到 ℝ 使得 i2 = -1。 (如果你喜欢代数，这相当于说 D = ℝ[x]/⟨x2⟩。)因此，D 的每个元素都是 a + bε 的形式，其中 a 和 b 是实数。对偶数的算术按您的预期工作:

(a + bε) ± (c + dε) = (a + c) ± (b + d)ε；和

(a + bε)(c + dε) = ac + bcε + adε + bdε2 = ac + (bc + ad)ε。

(由于 ε2 = 0，除法更加复杂，尽管您对复数使用的共轭乘法技巧仍然有效；请参阅 Wikipedia's explanation 了解更多信息。)

现在，为什么这些有用？直观地说，ε 就像一个无穷小，允许您用它计算导数。事实上，如果我们用不同的名字重写乘法规则，它就变成了

(f + f'ε)(g + g'ε) = fg + (f'g + fg')ε

那里的ε系数看起来很像 the product rule功能差异化产品!

那么，让我们弄清楚一大类函数会发生什么。由于我们忽略了上面的除法，假设我们有一些函数 f : ℝ → ℝ 由幂级数定义(可能是有限的，所以任何多项式都可以，就像 sin(x)、cos(x) 和 ex 之类的东西) .然后我们可以定义一个新函数 fD : D → D 以显而易见的方式:我们添加对偶数等，而不是添加实数，等等。然后我声明 fD(x + ε) = f(x) + f '(x)ε。首先，我们可以通过归纳证明，对于任何自然数 i，都是 (x + ε)i = xi + ixi-1ε 的情况；这将为 f(x) = xk 的情况建立我们的导数结果。在基本情况下，当 i = 0 时，这个等式显然成立。然后假设它对 i 成立，我们有

(x + ε)i+1 = (x + ε)(x + ε)i 通过分解 (x + ε)

的一个副本

= (x + ε)(xi + ixi-1ε) 由归纳假设

= xi+1 + (xi + x(ixi-1))ε 由对偶乘法的定义

= xi+1 + (i+1)xiε 通过简单代数。

事实上，这正是我们想要的。现在，考虑我们的幂级数 f，我们知道

f(x) = a0 + a1x + a2x2 + … + aixi + …

然后我们有

fD(x + ε) = a0 + a1(x + ε) + a2(x + ε)2 + … + ai(x + ε)i + …

= a0 + (a1x + a1ε) + (a2x2 + 2a2xε) + ... + (aixi + iaixi-1ε) + ... 由上述引理

= (a0 + a1x + a2x2 + … + aixi + …) + (a1ε + 2a2xε + … + iaixi-1ε + …) 由交换性

= (a0 + a1x + a2x2 + … + aixi + …) + (a1 + 2a2x + … + iaixi-1 + …)ε 通过分解出 ε

= f(x) + f'(x)ε 根据定义。

伟大的!所以对偶数(至少在这种情况下，但结果通常是正确的)可以为我们做微分。我们所要做的就是将原始函数应用于，不是实数 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

其中， as Wolfram Alpha can confirm , 正是正确的答案。

关于这些东西的更多信息肯定是可用的。我不是这方面的专家。我只是觉得这个想法真的很酷，所以我借此机会模仿我读过的内容并找出一两个简单的证明。 Dan Piponi 写了更多关于对偶数/自动微分的文章，包括 a post where, among other things, he shows a more general construction which allows for partial derivatives . Conal Elliott 有 a post where he shows how to compute derivative towers (f(x), f′(x), f″(x), …) in an analogous way . Wikipedia article on automatic differentiation linked above进入更多细节，包括一些其他方法。 (这显然是“正向模式自动微分”的一种形式，但“反向模式”也存在，而且显然可以更快。)

最后，还有 a Haskell wiki page on automatic differentiation ，它链接到一些文章——而且，重要的是， 一些 Hackage 软件包 !我从未使用过这些，但似乎 the ad package, by Edward Kmett是最完整的，处理多种不同的自动微分方式——结果他上传了那个包 after writing a package to properly answer another Stack Overflow question .

我确实想补充一件事。你说“但是，数据类型不应该代表函数(解析器除外)。”我不得不不同意这一点——将你的函数具体化为数据类型对于这方面的所有事情都非常有用。 (无论如何，是什么让解析器如此特别？)任何时候您有一个想要内省(introspection)的函数，将其具体化为一种数据类型都是一个不错的选择。例如，这里是符号微分的编码，很像上面的自动微分的编码:

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 !唯一需要放置导数相关代码的地方是新数据类型的定义和微分函数；您可以免费获得现有函数的衍生物。