Q&A
オートマトンと関数は違います。
eqDFTree は汎用ではありません。***その人が作った***決定性有限オートマトン(DF)の構造(Tree)の等価性(eq)を判定するもので、ここの質問とは全く無関係です。
素朴な疑問ですが、関数が等しいとはどういう状況のことをいうのでしょうか。
あるいは、関数の等価性についてどのように定義すれば良い（定義すべき）なのでしょうか。
例えば、関数f,gが等価であるとは、fとgの中で行なっている処理が等しいと定義すると、
次の２つの関数は、入出力は等しいですが異なる関数ということになります。
f x = x * 2 g x = x + x
また、関数f,gが等価であることを、それぞれの関数の入出力が等しいと定義すると、
すべてのソートアルゴリズムを使った関数bubbleSort, quickSort, mergeSortなどはすべて「同じ関数」ということになります。
もし、関数を、定義されているメモリ上のアドレス（ちょっと言い方が変ですが）によって等価性を判別しようとすると、同じ処理を行う関数を別の名前で２つ作成すると、それらは全く同じでありますが異なる関数ということになります。
色々な解釈があると思いますが、妥当な方法はあるのでしょうか。関数型プログラミングでは関数を第一級オブジェクトとして扱うことがあるので、関数同士の比較(==,!=)も定義できるのかと思い、質問させていただきます。
回答5件
0
ベストアンサー
関数の等価性についてどのように定義すれば良い（定義すべき）なのでしょうか
一言でいうと、目的に応じて定義します。
値の等価性（同値性）、参照の等価性（同一性）、
等価性にもいろいろありますが、プログラムの目的に応じて、
等価性を判定する関数やメソッドを利用、実装すれば良いのです。
これだけだとつまらないので、もう少し具体例を考えてみます。
関数f,gが等価であるとは、fとgの中で行なっている処理が等しいと定義すると、
次の２つの関数は、入出力は等しいですが異なる関数ということになります
しかし、こういう考え方もあります。
関数は写像なので、入力と出力が同じであれば同じ関数とみなしてよい。
これなら「f x = x * 2」と「g x = x + x」は同じ関数になります。
ここで「どちらの定義が正しいか」というよりは、
「その定義で何がしたいか」という方が重要です。
たとえば、コードを高速化したいときに、
より処理が早い同じ（値を返す）関数に差し替えたいとか。
除算が遅いので使わない式に書き替える、
といったことは実際に行われていますね。
等価性の判定の実装についても、入口だけ説明しておきます。
上でいった入出力の等価性を具体的にどう判定するかといえば、
入力を与えて出力を確かめればいいことになります。
たとえば、入力xが1のとき、出力yは2とか。
計算機は有限の範囲しか扱えず、無限の入出力試験は不可能です。
しかし実用上は足りることも多く、これは自動テストの考えです。
また、式変形で等価性を判定する道もあります。
自然数の乗法を数学的帰納法で定義すると、
n0 = 0
n(k+1) = (n*k)+n
問題の関数定義
f(x) = x*2
g(x) = x+x
上の乗法定義より、
x*(1+1) = (x1)+x
x2 = x+x
よってf(x) = g(x)
証明終
自然数とか加法とかの前提を端折った雑な証明ですが、
式変形で等価性を証明するイメージはつかめるでしょう。
プログラムで実装するのは記号処理が大変だと思いますが。
最後に、関数型言語を一言でいうとラムダ計算に基づく言語で、
そのラムダ計算は数学を抽象化したモデルなので、数学に近い言語です。
そこで関数型言語は数学の自動証明や証明支援に使われることがあります。
やはり無限が絡む領域では完全性がありませんが。
投稿2016/08/29 13:31
総合スコア5594
0
わかりやすくするために、+をplus、*をprodとして、数学的に定義してみます。(0以上の整数だけ考えます)
Haskell
1f x = prod x 2 2g x = plus x x 3prod x 0 = 0 4prod x n = plus x $ prod x $ pred n 5plus x 0 = x 6plus x n = succ $ plus x $ pred n 7-- succ は 1 多い数を、pred は 1 少ない数を返す関数
このようにすると、上に置いて、f xはg xと同じだと証明できます。
f x = prod x 2 = plus x $ prod x $ pred 2 = plus x $ prod x 1 = plus x $ plus x $ prod x $ pred 1 = plus x $ plus x $ prod x 0 = plus x $ plus x 0 = plus x x = g x -- pred 2 は 1 、pred 1 は 0 です。
ただ、実際の+と*が数学的に実装されているわけではない(掛け算を足し算で実装するわけがありません)ため、処理的には等価にはならないでしょう。数学としては等価にも関わらずです。
ということで、このような定義であれば関数の==を定義して同じであるというのはできそうな気がします。いかがでしょうか？
本来、数学的には
∀x f(x) = g(x) ⇔ f = g
と定義すべきなのでしょうが、全てのxを計算するための計算量が膨大すぎて非現実的です。f = g を述語的に証明すべきですが、どうやってその証明を作り上げられるかです。ある関数とある関数が等しい事を自動で証明できるのであれば、数学者は実はいらない…となりそうな気がします。
投稿2016/08/29 12:32
総合スコア21853
0
どういう用途で使うかによって、「等しさ」の概念も違ってきます。あまいほうから行くと、
- 同じ値を与えれば同じ結果を返す、という意味で「等しい」
- 上に加えて、所要時間や使うメモリなど、ほかの特性が（比較が必要な面で）「等しい」
- （JavaScriptなど関数がオブジェクトの言語で）オブジェクトとして「等しい」
のように、いくつも考えられます。真ん中については、たとえばソートであれば規模に応じた計算量やメモリ量がアルゴリズムによって違ってきますし、ハッシュ値の比較用に「どんな値を比較しても有意な時間差がでない」ことを要求される場面もあります。
なお、いちばん最初の「同じ値を与えれば同じ結果を返す」という意味での等しさは、有限の時間内で100%正しく判定する方法は存在しないことが証明されています。大雑把に言えば、「未解決問題の解がないか探し続け、見つけた段階で停止する関数」と「ただ無限ループする関数」を比較して、有意な結果が得られるならそちらのほうが驚きです。
投稿2016/08/29 11:49
編集2018/04/28 01:53
総合スコア147054
0
整数で 1 から n までの和を返す関数 sum(n) を
1..n のループを回して計算する実装と
n * (n + 1) / 2 で計算する実装を
等価とみなしたいですか？
おそらく正常な入力に対してはどちらも同じ値を返すでしょう。
でも、処理時間は両者で異なるでしょう。
この場合はいい例が思い当たりませんが、
内部実装が異なると 数値計算の誤差の具合や
オーバーフロー、アンダーフローなどのエラーが起こる条件も変わると思います。
プログラミングと数学は異なっています。
数学とプログラミングの差の例としては、２次元方程式の解があります。
解の公式をそのままコードにしたのでは、全く使い物にはなりません。
参考：
return x と return (0.1 + x - 0.1) は挙動が異なる可能性があるのです。
コードでの実装が異なるのに、全ての入力値 (特に float や double ) に対して、
同じ挙動をするかを調べることが可能かも不明です。
プログラムのコードが同じでも、コンパイラの差や 動作させる CPU によって挙動が異なる可能性もあるます。
プログラムの等価性は、考えれば考えるほど混乱します。
プログラムの等価性は、それを確認できる方法から逆に定義するしかないかもしれません。
投稿2016/08/29 13:17
総合スコア22328
0
もし仮に二つの関数F1とF2があった時、それぞれの
初期状態からどのような入力によって状態遷移を
させても状態の出力が同じであればF1,F2は等価で
あると判定する。
投稿2016/08/29 11:50
編集2016/08/30 15:19
総合スコア1630
あなたの回答
tips
プレビュー
2016/08/30 12:58