見るこの本ですが、関数型プログラミングのアルゴリズムデザインを紹介した本で、とても難しいのですが、面白いです。Calencdarのネタとして、これに出てくるアルゴリズムをScalaで実装してみたいと思います。「最小自由数」を求める一番シンプルなコード「最小自由数」ですが、とある自然数の集合(ここではListを使います)に含まれない数字のうち、一番小さいものです。自然数は、0以上の整数です。元のコードはこんなかんじです。一部、数学的な記号が使われていたので(∉)、変換しています。us(\)は、差集合を取る関数で、ゼロから始まる無限リスト([0..])から、対象の数のリストを引き算することで、答えを導き出しています。1ページ目からこんなコードが出てきてしまう本です。このコード、(\)の部分が、usの各要素に対して、vsを線形探索するため、O(n2)の比較回数が必要になります。これをO(n)にしてしまおうというのが、この章の趣旨のようです。ScalaのコードこのコードをScalaのコードに直すとこんな感じです。!xs.contains(x)).head}差集合を取る関数を分離するのが面倒だったので一本にまとめてしまいました。まとめてもHaskellほど可動性が落ちる感じがしなかったので、Scala優秀ですね(適当)。Scalaの方が圧倒的にわかりやすいと感じるのは、きっと僕がオブ脳(オブジェクト指向脳)だからでしょう。本では、2つの解法を紹介しています。ひとつは、Arrayを使った解法で、もうひとつは分割統治法と呼ばれるもの*1。Arrayを使った方法ですが、Haskellでは、Arrayもimmutableなので、多少厄介みたいです。elemsHaskellのArrayは、Cの配列やScalaのArrayと違い、KeyとValueのペアの連想配列のようになっています。上記の例では、Intとインデックスとして、Boolをバリューとした配列を受け取っています。idで先頭から中身がTrueの連続した要素を取り出し、その長さを答えとしています。本文に書かれていますが、この方法でのminfreeは下記のように定義されます。Bool」になるのでしょう。xs今回のプログラムコードで一番難しいのが、この「accumArrray」です。本には「この関数はいささか手強い」と書いてありますが、いささかってレベルじゃねぇ。5生成されるArrayHoogleで調べた、シグネチャーはこんなかんじです。伝わるかわからないですが、説明を試みます。最終的に欲しいのは、Arrayです。Haskellは純粋関数型言語なので、Arrayのような(定数時間で要素にアクセスできるようなソリッドな)データ構造を順次構築すると非常に非効率です。そのため生成関数を使って一気に生成してあげるのが効率的ということなんだと思います。これはそのための関数で、Listを入力に貰って、foldに似た変換処理を行いArrayを生成します。n)を渡して、0からnの範囲*2を2Falseで初期化しています。a)]のiのインデックスの所だけ呼ばれます。True)で結果をTrueにします。インデックスが当たらなかった部分は、Falseとして残るので、結果としてxsの要素の数字をTrueに変更した配列が手に入ります。True...]この様な配列が手にはいれは、後は、先頭からTrueの要素を数えていけば答えが出るって寸法です。ScalaのコードScalaのArrayはデフォルトでmutableなので、accumArrayを再実装するようなことはしませんでした*3。そのため、Scalaのコードのほうがシンプルで直感的になっていますね。Quickソートに代表されるような、リストを分割していって再びまとめていくような方法です。集合を分割した際の差集合の計算が持つ性質を利用して、分割と探索を繰り返していくというHaskellではよく見かけるタイプのコードです。us正直、aとかbとかnとかmとか出てきて、きっちり詰めて考察する気が起きないですが(おい)、aのポイントを1/2に切り詰めながら値を追い詰めていく例のアレですね。partitionは、リストを条件(<b)にしたがって2つに分割する関数で、線形探索なのでO(n)ですね。あと、lengthがO(n)なので、全体でもO(n)なのでしょう。Scalaのコードこちらは、何も考えずに完全移植できました。us))}関数の引数でのパタンマッチが無いのと、関数のガードが無いので、if文になっているあたりが野暮ったいですが、ほぼ1対1で対応しています。珠玉のアルゴリズムデザイン」をまだ読んでいない人に訴えたいのは、この問題を皮切りに、難易度を加速させながら第30章までアルゴリズムの解説が続きます。みんな一緒に、この辛さを味わおうぜ!!!Scalaをまだ初めていない人に訴えたいのは、Scalaを使えば、Javaジャバーなオブジェクト指向脳にも読みやすいプログラムコードでHaskellっぽいこともできちゃうし、色々楽しい。コンパイル速度が辛かったり、マクロとかscalazとか、ちょっぴり怖い人も多いけど、私は元気です(おい)。私は元気です!!おしまい。*1:先の方のページをパラパラめくるとこの「分割統治」という単語が毎回出てきているので重要な概念なんでしょう*2:最小自由数はxsの長さよりも大きくならない。その2さて、前回の続きです。はてなブログProシステム開発の世界で15年の山の民による、世界のカタチを探求するブログ。(4)はてなブログをはじめよう!qtamakiさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。