Haskell中的函数平等 [英] Equality of functions in Haskell

问题描述

我试图定义一个函数，它需要一个 Double - > Double 函数并返回其数学导数。我已经尝试做以下事情：

  der ::（Double  - > Double） - > （Double  - > Double）
 der f 
 | f == exp = exp 
 |否则= undefined 
  

但Haskell不支持 == 打开双击 - > Double 值。在Haskell中，我试图做什么是不可能的？解析方案

是的，你在Haskell中试图做什么是不可能的，并且一般来说：决定两个函数对于所有可能的输入是否相等（不仅仅是检查每个输入值，如果这甚至是可能的话）相当于解决停机问题。

但是，在您的具体情况中，您可以使用模拟 Double 的自定义类型来避开它（即具有相同的实例，因此可用于替代它），而不是对一个数字进行求值，它构造了函数所做操作的抽象表示。 Expr 表示数学函数定义 f（x）= ... 的右侧。

  data Expr = X | Const Double | 
添加Expr Expr | Mult Expr Expr | 
取消| Expr |逆Expr | 
 Exp Expr |记录Expr | Sin Expr | ... 
 deriving（Show，Eq）
 
实例Num Expr其中
（+）= Add 
（*）= Mult 
 ... 
实例Fractional Expr其中
 recip =反转
 ... 
实例Floating Expr其中
 pi =常量pi 
 exp = Exp 
 log = Log 
 sin = Sin 
 ... 
  

然后，您可以定义在函数和 Expr s之间进行转换的转换函数：



  fromFunction ::浮动a => （a  - > a） - > Expr 
 fromFunction f = f X 
 
 toFunction :: Expr  - > （Double  - > Double）
 toFunction X = \ x  - > x 
 toFunction（Const a）= const a 
 toFunction（Plus a b）= \ x  - > （toFunction ax）+（toFunction bx）
 ... 
  

您也可以定义一个函数 diff :: Expr - > Expr 区分表达式：



  diff X = Const 1 
 diff（Const _ ）= Const 0 
 diff（Plus ab）= Plus（diff a）（diff b）
 diff（Exp a）= Mult（diff a）（Exp a）
 ... 
  

具有所有这些部分意味着您可以区分（某些）功能，例如

  fx = sin x + cos x * exp x 
 f'= toFunction。差异。 fromFunction $ f 
  

注意事项：

• 这通常不起作用，
  
• 定义完整的 Eq 实例对于 Expr 是棘手的（它相当于Halting问题，因为它基本上是询问两个函数是否相等），
  
• 还没有真正测试过这些代码，
  
• 分化和重构是在运行时完成的，所以得到的函数很可能非常慢。

I am trying to define a function which would take a Double -> Double function and return its mathematical derivative. I have tried doing the following:

der :: (Double -> Double) -> (Double -> Double)
der f
    | f == exp = exp
    | otherwise = undefined

but Haskell does not support == on Double -> Double values. Is what I am trying to do impossible in Haskell?

解决方案

Yes, what you are trying to do is impossible in Haskell, and in general: deciding whether two functions are equal for all possible inputs (without just checking every input value, if that is even possible) is equivalent to solving the Halting problem.

However, in your specific case, you can get around it, using a custom type that simulates a Double (i.e. has the same instances, and so can be used in place of it) but instead of evaluating to a number, it constructs an abstract representation of the operations the functions does. Expr represents the right-hand side of a mathematical function definition f(x) = ....

data Expr = X | Const Double |
            Add Expr Expr | Mult Expr Expr |
            Negate Expr | Inverse Expr |
            Exp Expr | Log Expr | Sin Expr | ...
       deriving (Show, Eq)

instance Num Expr where
    (+) = Add
    (*) = Mult
    ...
instance Fractional Expr where
    recip = Inverse
    ...
instance Floating Expr where
    pi = Const pi
    exp = Exp
    log = Log
    sin = Sin
    ...

Then, you can define conversion functions that convert between functions and Exprs:

fromFunction :: Floating a => (a -> a) -> Expr
fromFunction f = f X

toFunction :: Expr -> (Double -> Double)
toFunction X = \x -> x
toFunction (Const a) = const a
toFunction (Plus a b) = \x -> (toFunction a x) + (toFunction b x)
...

You can also define a function diff :: Expr -> Expr that differentiates the expression:

diff X = Const 1
diff (Const _) = Const 0
diff (Plus a b) = Plus (diff a) (diff b)
diff (Exp a) = Mult (diff a) (Exp a)
...

Having all these parts should mean that you can differentiate (some) functions, e.g.

f x = sin x + cos x * exp x
f' = toFunction . diff . fromFunction $ f

Caveats:

• this won't work in general,
• defining a complete Eq instance for Expr is tricky (it is equivalent to the Halting problem, since it is basically asking if two functions are equal),
• I haven't actually tested any of this code,
• the differentiation and reconstruction are done at runtime, so the resulting function is highly likely to be very slow.

这篇关于Haskell中的函数平等的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！