さんぽみち

なにか思いついたときとかに気まぐれに更新されます。

Haskellの勉強 その0

Haskell 暗号 学習の足跡

はじめに

　関数型プログラミング言語であるHaskellを最近勉強してます。

　動機としては、圏論と関数型プログラミング言語の関係を聞いて、そういえば関数型の言語ってやったことなかったなーって思ったから。

　手続型の言語しか触ったことがなかったので考え方がまるで違ってギャップが楽しい毎日です。

学習目的

　・関数型プログラミングの思想を雰囲気だけでもつかみ、思考の幅を広げる

　・圏論の基礎を身に着ける

学習方法

　とりあえずの学習方法としては、RSA暗号をさくっとべたべたな方法で実装した後に、Haskellらしい概念を取り入れていく方法でやります。

　RSA暗号を題材に選んだ理由はいくつかあって、一つ目がCTFやってたおかげでRubyやらC#で実装したことがあるため、手続型との対比を行いやすいため。

　二つ目が、ぱっと思いついた処理の中で、処理が短い割に数式を処理に落とし込むことが多いため。

　三つ目が、RSA暗号は平文空間と暗号文空間が乗法について準同型であるため、圏論が根っこにあるHaskellでは何か面白いことができるかもと思ったため。

 

 おわりに

　大体こんな感じ！

　RSA暗号について深く書くつもりはないので、気になる方はwikipedia先生とか参考のURLをのぞいてみてください。

参考

まいとう情報通信研究会(2003) はじめに | サルにも分かるRSA暗号

　初めてRSA暗号と出会った直後にお世話になったサイトです。

　前提知識がほとんど必要なく、頑張れば中学生でも雰囲気をつかむことができます。

神戸大学 高橋真研究室(2015) RSA暗号

　RSA暗号を実装するとき、計算結果が正しいかの答え合わせをここで行ってます。

　説明も簡潔で分かりやすく、試しながら学べて参考になると思います。

比較演算を行わないバブルソート

C# アルゴリズム

はじめに

　とりあえず何か書きたかったので、一発ネタで前に作った比較演算を行わないバブルソート。

　だいぶ前に書いたので今見ると無駄が多い！！

　全体を通して言えることだけども、数字に 1 を掛けると変化せず、 0 を掛けると 0 へつぶれることを利用して、比較せずに数字を選択しています。

　以下簡単な解説を。

各メソッドの概要

　引数が 0 であれば 0 を返し、それ以外であれば 1 を返すメソッドです。

　0 以外の任意の整数 n において、これの二の補数を m として、

　　n or m

　をとると必ず最上位ビットが立ち、0 の場合のみ立たないことを利用して判断しています。

　今回メインとなるメソッドです。

　0 または自然数 numA, numB のうち、大きな数字を返すメソッドです。

　まずは、符号なしなので最上位ビットを比較することでどちらが大きな数字であるか判断します。

　numA, numB いずれか一方のみの最上位ビットが立っていた場合は、立っていた値が残り、同じ場合であった場合は 0 となります。

　次に、差をとって比較します。

　符号なし整数での減算は、被減数が減数と比べて小さい場合はオーバーフローして最上位ビットが立ちます。

　numA, numB が違う値であればこの最上位ビットを見ることで、どちらが大きな値であるか判断できます。

　次に、numA, numB が等しかった場合を考慮して、等しければ適当に numA を残します。

　最後に、これまでの計算結果をすべて足し合わせます。

　それぞれの計算結果は、大きな値が確定できた場合のみ大きな値が、確定できなかった場合は 0 が残っているので、足すことで正しい結果が得られます。

 　Maxメソッドと同様に、逆のことを行っているだけです。

　符号付き整数を、大小関係そのままに符号なし整数と相互変換するメソッド達です。

　普通にキャストすると、符号付き整数は補数表現されたビット列になるので、そこへ最上位ビットのみ立てた数値と足すだけです。

  • BubbleSortActionデリゲート

　ソートするためにはインデックスを使用して配列にアクセスしなければなりません。

　よって条件を付けて何らかの形でループさせてインデックスを操作しなければなりませんが、比較演算を行わない縛りであるため通常のループ構文は使えません。

　そこで、再帰によりループを再現し、2 要素のデリゲート配列に対するインデックスを切り替えることで 継続：終了 をスイッチします。

　スタックを大量に使うので、なるべく節約するために引数は参照渡しです。

　クラス変数にしないことで、一応スレッドセーフです。

　再帰的にバブルソートを行うメソッドです。

　再帰なのを除けば何の変哲もないバブルソートです。

　インデックスが一回りすればデリゲートが切り替わるように細工してあります。

　再帰を終了させるためのメソッドです。

　out 修飾子は値を代入しなければエラーとなるため、ダミーで初期化します。

　バブルソートを行うための入口です。

　引数で渡す領域の初期化を行って再帰を始めます。

 

　以上、大雑把な説明でした。

おわりに

　確かどこかにLargeメソッドとSmallメソッドを追加して書き換えたのがあったはずだけど見当たらないので見つけたらそっちで書き直す。。。

　この再帰を使った方法でマージソートが実装できる気がしたからやってみようと思ってたはずだけども手付かずなので、気が向いたら書きます！