如何比较相等性两种功能，如（λx.2* X）==（λx.x+ X）？如何比较相等性两种功能，如（λx

有没有办法比较两个函数的平等？ 例如， (λx.2*x) == (λx.x+x)应返回true，因为这些都是明显等价的。

Answer 1:

这几乎众所周知，一般功能平等是一般不可判定的，所以你必须选择那些你感兴趣的问题的一个子集，你可能会考虑一些局部的解决方案：

• Presburger算术是一阶逻辑+算术的判定片断。
• 在宇宙包提供了功能相等测试与有限域总功能。
• 您可以检查你的职责是建立在一整套的投入相等，并将其视为对未经测试输入平等的证据; 检查出快速检查 。
• SMT求解器做出最大的努力，有时回答“不知道”，而不是“等于”或“不等于”。 有几个绑定到Hackage SMT求解器; 我没有足够的经验，建议最好之一，但托马斯M DuBuisson暗示SBV 。
• 有对决定功能平等和紧凑的功能的其他东西研究一个有趣的线; 这项研究的基础在博客文章中描述了看似不可能的功能程序 。 （请注意，紧凑是一个非常强大和非常微妙的状态！这不是一个最Haskell函数满足。）
• 如果你知道你的函数是线性的，你可以找到源空间的基础; 那么每一个功能都有一个唯一的矩阵表示。
• 你可以尝试定义自己的表达式语言，证明等价是可判定此语言，然后嵌入在Haskell该语言。 这是最灵活的，但也是最困难的方式取得进展。

Answer 2:

这是一般的不可判定的，而是一个合适的子集，可以有效地使用SMT求解器确实做到今天：

$ ghci
GHCi, version 8.0.1: http://www.haskell.org/ghc/  :? for help
Prelude> :m Data.SBV
Prelude Data.SBV> (\x ->  2 * x) === (\x -> x + x :: SInteger)
Q.E.D.
Prelude Data.SBV> (\x ->  2 * x) === (\x -> 1 + x + x :: SInteger)
Falsifiable. Counter-example:
  s0 = 0 :: Integer

有关详细信息，请参阅： https://hackage.haskell.org/package/sbv

Answer 3:

除了对方的回答给定的实际的例子，让我们挑选的类型lambda演算表达功能的子集; 我们还可以让积和类型。 虽然检查两项功能是否相等可以简单如把它们应用到一个变量，比较的结果 ，我们不能建立平等函数编程语言本身 。

ETA： λProlog是逻辑的编程语言用于操纵（类型演算）功能。

Answer 4:

2年过去了，但我想一点点的话到这个问题。 本来，我问，如果有任何的方式来告诉我们，如果(λx.2*x)等于(λx.x+x) 在λ演算加法和乘法可以被定义为：

add = (a b c -> (a b (a b c)))
mul = (a b c -> (a (b c)))

现在，如果你正常化以下条款：

add_x_x = (λx . (add x x))
mul_x_2 = (mul (λf x . (f (f x)))

你得到：

result = (a b c -> (a b (a b c)))

对于这两种方案。 由于他们的正常形式是相等的，这两个方案都显得相等。 虽然这并不在一般的工作，但它在实践中许多方面的工作。 (λx.(mul 2 (mul 3 x))和(λx.(mul 6 x))都具有相同的正常形式，例如。

Answer 5:

在与像数学符号计算语言：

或C＃与计算机代数库 ：

MathObject f(MathObject x) => x + x;
MathObject g(MathObject x) => 2 * x;

{
    var x = new Symbol("x");

    Console.WriteLine(f(x) == g(x));
}

在控制台上述显示器“真”。

Answer 6:

证明两个函数等于为一般不可判定的，但仍然可以证明在特殊情况下，功能性的平等，如你的问题。

下面是一个示例证明精益

def foo : (λ x, 2 * x) = (λ x, x + x) :=
begin
  apply funext, intro x,
  cases x,
  { refl },
  { simp,
    dsimp [has_mul.mul, nat.mul],
    have zz : ∀ a : nat, 0 + a = a := by simp,
    rw zz }
end

人们可以做同样在其他依赖性类型的语言，如勒柯克，阿格达，伊德里斯。

以上是一种战术风格的证明。 实际的定义foo获取生成（证明）是相当用手写成了一口：

def foo : (λ (x : ℕ), 2 * x) = λ (x : ℕ), x + x :=
funext
  (λ (x : ℕ),
     nat.cases_on x (eq.refl (2 * 0))
       (λ (a : ℕ),
          eq.mpr
            (id_locked
               ((λ (a a_1 : ℕ) (e_1 : a = a_1) (a_2 a_3 : ℕ) (e_2 : a_2 = a_3), congr (congr_arg eq e_1) e_2)
                  (2 * nat.succ a)
                  (nat.succ a * 2)
                  (mul_comm 2 (nat.succ a))
                  (nat.succ a + nat.succ a)
                  (nat.succ a + nat.succ a)
                  (eq.refl (nat.succ a + nat.succ a))))
            (id_locked
               (eq.mpr
                  (id_locked
                     (eq.rec (eq.refl (0 + nat.succ a + nat.succ a = nat.succ a + nat.succ a))
                        (eq.mpr
                           (id_locked
                              (eq.trans
                                 (forall_congr_eq
                                    (λ (a : ℕ),
                                       eq.trans
                                         ((λ (a a_1 : ℕ) (e_1 : a = a_1) (a_2 a_3 : ℕ) (e_2 : a_2 = a_3),
                                             congr (congr_arg eq e_1) e_2)
                                            (0 + a)
                                            a
                                            (zero_add a)
                                            a
                                            a
                                            (eq.refl a))
                                         (propext (eq_self_iff_true a))))
                                 (propext (implies_true_iff ℕ))))
                           trivial
                           (nat.succ a))))
                  (eq.refl (nat.succ a + nat.succ a))))))

文章来源: How to compare two functions for equivalence, as in (λx.2*x) == (λx.x+x)?