プログラミングで同値関係が分かる!

数学の「関係と集合」まで進んだら、同値関係(Equivalence relation)の説明で、反射律、対称律、推移律、反対称律が出てきました。教科書の言い回しは難しくて何言っているのか分からなかったのですが、プログラミングで考えれば簡単なことでした。関係演算子の機能チェックをするルールを律と言っているだけでした。

プログラミングで使う演算子のおさらい

私たちは普段何気なく使っていますが、演算子はいくつかグループに分けられます。それでイコール記号や大なり小なりは関係演算子と言います。

算術演算子 + - * / %など

関係演算子 == != < <= > >=

論理演算子 && || !

関数型言語の演算子を見てみる

F#のような関数型プログラミング言語では、算術演算子、関係演算子、論理演算子は、どれも関数として使えます。1 + 1のような加算演算子は、中置記法で使いますが、()を使うと前置記法にできます。この前置記法は、プログラミングで私たちが良く作る関数と同じ順番です。関数名、第一引数、第二引数となっています。

JavaScriptの場合は、add関数を作ってx + yをその中に書けば、算術演算子+を別名のadd関数として作れます。

関数型言語の場合は、先ほどの前置記法があるので、add関数で包むという感じではなく、別名を用意する感じです。以下のようになります。

 

ここでひとつ分かることがあります。私たちはプログラミングで演算子を使っていますが、関数で演算子を包んであげれば、関数として使えて、add(x,y)のように、名前を前に持って来ることができます。

等号の関数を作ってみる

JavaScriptの場合は、==で、値が同じかどうかを比較するので、この演算子をeq関数で包めば等号の関数が作れます。

F#の場合は、=が値が同じかどうかを比較します。かなり省略した表記なので、なれないと見づらいです。

ここまでで、add関数、eq関数を作ってみました。これらは+演算子や=演算子と同じように使えます。

K演算子を作ってみる

謎のK演算子を作ってみます。といっても、以下のようにプログラミング言語に演算子Kを追加することはできません。

ですが、add関数やeq関数と同様に、K関数を作って演算子に見立てることはできます。K演算子の中身はなんでもいいのですが、「3で割ったときのあまりが等しい」という演算子にしてみます。

JavaScriptだと以下のような感じです。

F#だと

K関数(K演算子)を作ってみました。ここで問題ですが、K関数(K演算子)は、どのような機能を持っているのでしょうか、=演算子と同じ機能を持っているのでしょうか、それとも>演算子と同じ機能でしょうか、>=と同じ機能でしょうか。

この性質チェックをするのが、数学でいう、反射律、対称律、推移律、反対称律です。何々律というのは実際にはもっとたくさんありますが、教科書では必要な部分しか説明していません。

それで、反射律、対称律、推移律の3つをパスできれば、同値関係つまり、プログラミングの==記号と同じですという事ができます。もしK関数(K演算子)が、同値関係なら、==演算子としても使えるという事になります。

また順序関係もあり、こちらは、反射律、推移律、反対称律、全順序律を満たす必要があります。もしK関数(K演算子)が、順序関係なら、大小の比較にも使えるという事になります。

書きかけのソースコード

正しくない部分があると思いますが、ひとまず雰囲気だけでも分かると思いますので、書きかけのソースコードも載せておきます。

 

 まとめ

数学の問題を解くのではなく、どうにかしてプログラミングの問題にしてしまえば続けられるのが分かってきました。

参考資料

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA