関数が等しいとは？

素朴な疑問ですが、関数が等しいとはどういう状況のことをいうのでしょうか。
あるいは、関数の等価性についてどのように定義すれば良い（定義すべき）なのでしょうか。

例えば、関数f,gが等価であるとは、fとgの中で行なっている処理が等しいと定義すると、
次の２つの関数は、入出力は等しいですが異なる関数ということになります。

f x = x * 2
g x = x + x

また、関数f,gが等価であることを、それぞれの関数の入出力が等しいと定義すると、
すべてのソートアルゴリズムを使った関数bubbleSort, quickSort, mergeSortなどはすべて「同じ関数」ということになります。

もし、関数を、定義されているメモリ上のアドレス（ちょっと言い方が変ですが）によって等価性を判別しようとすると、同じ処理を行う関数を別の名前で２つ作成すると、それらは全く同じでありますが異なる関数ということになります。

色々な解釈があると思いますが、妥当な方法はあるのでしょうか。関数型プログラミングでは関数を第一級オブジェクトとして扱うことがあるので、関数同士の比較(==,!=)も定義できるのかと思い、質問させていただきます。

行動規範の内容に同意します

回答5件

ベストアンサー

関数の等価性についてどのように定義すれば良い（定義すべき）なのでしょうか

一言でいうと、目的に応じて定義します。

値の等価性（同値性）、参照の等価性（同一性）、
等価性にもいろいろありますが、プログラムの目的に応じて、
等価性を判定する関数やメソッドを利用、実装すれば良いのです。

これだけだとつまらないので、もう少し具体例を考えてみます。

関数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

LLman

総合スコア5592

t-miyazaki

2016/08/30 12:58

なるほど、端的に言えば、目的に応じて定義するのですね。皆様の回答を総合すると、あえて漠然と定義するのであれば、関数の入力と出力が同じならば同じ関数としてよいという定義を採用するのが妥当かと理解しました。 "関数は写像なので、入力と出力が同じであれば同じ関数とみなしてよい。これなら「f x = x * 2」と「g x = x + x」は同じ関数になります。 " これは私の質問文における２つ目の例(ソート関数)のことですね。今回の質問では、等価性を判定するにはどう考えればいいか、ということまでで、それをプログラム的に実装することまでは考えていませんでしたが、やはり無限を扱う関数についてはそれを実現できるアルゴリズムはないと思います。それが実装できれば面白いのですが、ここでは概念として理解するにとどめておきたいと思います。ありがとうございました。他の方々もご回答ありがとうございました。

行動規範の内容に同意します

わかりやすくするために、+を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

raccy

総合スコア21735

どういう用途で使うかによって、「等しさ」の概念も違ってきます。あまいほうから行くと、

同じ値を与えれば同じ結果を返す、という意味で「等しい」
上に加えて、所要時間や使うメモリなど、ほかの特性が（比較が必要な面で）「等しい」
（JavaScriptなど関数がオブジェクトの言語で）オブジェクトとして「等しい」

のように、いくつも考えられます。真ん中については、たとえばソートであれば規模に応じた計算量やメモリ量がアルゴリズムによって違ってきますし、ハッシュ値の比較用に「どんな値を比較しても有意な時間差がでない」ことを要求される場面もあります。

なお、いちばん最初の「同じ値を与えれば同じ結果を返す」という意味での等しさは、有限の時間内で100%正しく判定する方法は存在しないことが証明されています。大雑把に言えば、「未解決問題の解がないか探し続け、見つけた段階で停止する関数」と「ただ無限ループする関数」を比較して、有意な結果が得られるならそちらのほうが驚きです。

投稿2016/08/29 11:49

編集2018/04/28 01:53