(λx.2*x) == (λx.x+x) のように、2つの関数を等価に比較するにはどうしたらよいでしょうか。

質問

2つの関数を等価に比較する方法はありますか？例えば (λx.2*x) == (λx.x+x) は真を返すはずです。なぜならそれらは明らかに等価だからです。

どのように解決するのですか？

一般的な関数の等式が決定不可能であることはかなりよく知られているので、興味のある問題の部分集合を選ぶ必要があるでしょう。これらの部分解答のいくつかを検討するとよいでしょう。

• Presburger 算術 は一階論理＋算術の決定可能な断片である。
• は 宇宙 パッケージは、有限領域を持つ全関数に対する関数の等質性テストを提供します。
• 関数が多くの入力で等しいことを確認し、それをテストされていない入力での等しさの証拠として扱うことができます。 クイックチェック .
• SMTソルバーは最善の努力をしますが、時には "equal" や "not equal" の代わりに "don't know" を応答することがあります。HackageにはSMTソルバーのバインディングがいくつかありますが、私はベストなものを提案できるほど経験がないので、Thomas M. DuBuissonは次のように提案しています。 sbv .
• コンパクトな関数における関数の等価性などの決定に関する楽しい研究ラインがあります。この研究の基本は、ブログ記事 一見不可能に見える関数型プログラム . (コンパクトであることは、非常に強く、非常に微妙な条件であることに注意してください！）。ほとんどのHaskell関数が満たすものではありません)。
• 関数が線形であることが分かっている場合、ソース空間の基底を見つけることができます; そうすると、すべての関数は一意の行列表現を持ちます。
• あなた自身の式言語を定義し、その言語で等価性が決定可能であることを証明し、その言語をHaskellに埋め込むことを試みることができます。これは最も柔軟な方法ですが、進歩するのが最も難しい方法でもあります。