セカイノカタチ

世界のカタチを探求するブログ。関数型言語に興味があり、HaskellやScalaを勉強中。最近はカメラの話題も多め

「関数プログラミング 珠玉のアルゴリズムデザイン」をScalaで実装してみる

Haskell Scala アルゴリズム

Scala Advent Calendar 2014 - Qiita14日目の記事です。

昨日の記事は、 @gakuzzzz さんの play2-auth で OpenID とか Twitter OAuth とか OAuth2.0 とか でした。

さて、今日のネタです。。。

関数プログラミング 珠玉のアルゴリズムデザイン

関数プログラミング 珠玉のアルゴリズムデザイン

この本ですが、関数型プログラミングのアルゴリズムデザインを紹介した本で、とても難しいのですが、面白いです。

Advent Calencdarのネタとして、これに出てくるアルゴリズムをScalaで実装してみたいと思います。

お題は、一番簡単そうな「第１章 最小自由数」です。

「最小自由数」を求める一番シンプルなコード

「最小自由数」ですが、とある自然数の集合(ここではListを使います)に含まれない数字のうち、一番小さいものです。

自然数は、0以上の整数です。

元のコードはこんなかんじです。一部、数学的な記号が使われていたので(∉)、変換しています。

minfree :: [Int] -> Int
minfree xs = head ([0..] \\ xs)

(\\) :: Eq a => [a] -> [a] -> [a]
us \\ vs = filter (not . flip elem vs) us

(\)は、差集合を取る関数で、ゼロから始まる無限リスト([0..])から、対象の数のリストを引き算することで、答えを導き出しています。

さらっと、1ページ目からこんなコードが出てきてしまう本です。お茶目ですね。

このコード、(\)の部分が、usの各要素に対して、vsを線形探索するため、O(n2)の比較回数が必要になります。これをO(n)にしてしまおうというのが、この章の趣旨のようです。

Scalaのコード

このコードをScalaのコードに直すとこんな感じです。

def minfree(xs: List[Int]): Int = {
  Stream.from(0).filter(x => !xs.contains(x)).head
}

差集合を取る関数を分離するのが面倒だったので一本にまとめてしまいました。

まとめてもHaskellほど可動性が落ちる感じがしなかったので、Scala優秀ですね(適当)。

Scalaの方が圧倒的にわかりやすいと感じるのは、きっと僕がオブ脳(オブジェクト指向脳)だからでしょう。

Arrayを使った解法

本では、2つの解法を紹介しています。

ひとつは、Arrayを使った解法で、もうひとつは分割統治法と呼ばれるもの*1。

Arrayを使った方法ですが、Haskellでは、Arrayもimmutableなので、多少厄介みたいです。

search :: Array Int Bool -> Int
search = length . takeWhile id . elems

HaskellのArrayは、Cの配列やScalaのArrayと違い、KeyとValueのペアの連想配列のようになっています。上記の例では、Intとインデックスとして、Boolをバリューとした配列を受け取っています。

そして、elemsでいきなりインデックスを捨て、ただのBoolのListに変換し、takeWhile idで先頭から中身がTrueの連続した要素を取り出し、その長さを答えとしています。

さらっと本文に書かれていますが、この方法でのminfreeは下記のように定義されます。

minfree = search . checklist

checklistは、まだ紹介されていないですが、戻りの型が「Array Int Bool」になるのでしょう。

checklist :: [Int] -> Array Int Bool
checklist xs = accumArray (||) False (0, n)
               (zip (filter (<= n) xs) (repeat True))
               where n = length xs

今回のプログラムコードで一番難しいのが、この「accumArrray」です。

本には「この関数はいささか手強い」と書いてありますが、いささかってレベルじゃねぇ。(#ﾟДﾟ)ｺﾞﾙｧ!!

accumArray :: Ix i =>
    (e -> a -> e) -- ①累積関数
    -> e          -- ②初期値
    -> (i, i)     -- ③(生成され探索される)配列の範囲
    -> [(i, a)]   -- ④元データ(Arrayを構成するKey/Valueのタプルをリスト化したもの)
    -> Array i e  -- ⑤生成されるArray

Hoogleで調べた、シグネチャーはこんなかんじです。

伝わるかわからないですが、説明を試みます。

まず、最終的に欲しいのは、Arrayです。

Haskellは純粋関数型言語なので、Arrayのような(定数時間で要素にアクセスできるようなソリッドな)データ構造を順次構築すると非常に非効率です。

そのため生成関数を使って一気に生成してあげるのが効率的ということなんだと思います。

そして、これはそのための関数で、Listを入力に貰って、foldに似た変換処理を行いArrayを生成します。

今回の例では、③に(0, n)を渡して、0からnの範囲*2を②Falseで初期化しています。

そして、①は、(0, n)の範囲の中で④[(i, a)]のiのインデックスの所だけ呼ばれます。

つまり、④(zip (filter (<= n) xs) (repeat True))で「xsからn以下の要素を抜き出し、Trueとペアにする」処理を行い[(12,True),(8,True)...]のようなListを作り、当該のインデックスの部分を①(False || True)で結果をTrueにします。

インデックスが当たらなかった部分は、Falseとして残るので、結果としてxsの要素の数字をTrueに変更した配列が手に入ります。

[True, True, True, True, True, True, False, False, True, True...]

この様な配列が手にはいれは、後は、先頭からTrueの要素を数えていけば答えが出るって寸法です。

そしてScalaのコード

ScalaのArrayはデフォルトでmutableなので、accumArrayを再実装するようなことはしませんでした*3。

そのため、Scalaのコードのほうがシンプルで直感的になっていますね。多分。

def minfree2(xs: List[Int]): Int = {
  search(checklist(xs))
}

def search(xs: Array[Boolean]): Int = (xs.takeWhile { identity _ }).length

def checklist(xs: List[Int]): Array[Boolean] = {
  val n = xs.length
  val ar = Array.fill(n + 1)(false)
  xs.filter(_ <= n).foreach { ar(_) = true }
  ar
}

分割統治法

分割統治法は、Quickソートに代表されるような、リストを分割していって再びまとめていくような方法です。

集合を分割した際の差集合の計算が持つ性質を利用して、分割と探索を繰り返していくというHaskellではよく見かけるタイプのコードです。

minfree xs = minfrom 0 (length xs, xs)

minfrom a (n, xs) | n == 0     = a
                  | m == b - a = minfrom b (n - m, vs)
                  | otherwise  = minfrom a (m, us)
                    where (us, vs) = partition (<b) xs
                          b        = a + 1 + n `div` 2
                          m        = length us

正直、aとかbとかnとかmとか出てきて、きっちり詰めて考察する気が起きないですが(おい)、aのポイントを1/2に切り詰めながら値を追い詰めていく例のアレですね。

partitionは、リストを条件(<b)にしたがって２つに分割する関数で、線形探索なのでO(n)ですね。

あと、lengthがO(n)なので、全体でもO(n)なのでしょう。

Scalaのコード

こちらは、何も考えずに完全移植できました。

def minfree3(xs: List[Int]): Int = minfrom(0, (xs.length, xs))

def minfrom(a: Int, par: (Int, List[Int])): Int = {
  val (n, xs) = par
  val b = a + 1 + n / 2
  val (us, vs) = xs.partition { _ < b }
  val m = us.length

  if (n == 0) a
  else if (m == b - a) minfrom(b, (n - m, vs))
  else minfrom(a, (m, us))
}

関数の引数でのパタンマッチが無いのと、関数のガードが無いので、if文になっているあたりが野暮ったいですが、ほぼ１対１で対応しています。

この記事が訴えたかったこと

「関数プログラミング 珠玉のアルゴリズムデザイン」をまだ読んでいない人に訴えたいのは、この問題を皮切りに、難易度を加速させながら第30章までアルゴリズムの解説が続きます。正直とても辛いです(おい)。

みんな一緒に、この辛さを味わおうぜ！！！

Scalaをまだ初めていない人に訴えたいのは、Scalaを使えば、Javaジャバーなオブジェクト指向脳にも読みやすいプログラムコードでHaskellっぽいこともできちゃうし、色々楽しい。コンパイル速度が辛かったり、マクロとかscalazとか、ちょっぴり怖い人も多いけど、私は元気です(おい)。

私は元気です！！

おしまい。

*1:先の方のページをパラパラめくるとこの「分割統治」という単語が毎回出てきているので重要な概念なんでしょう

*2:最小自由数はxsの長さよりも大きくならない。0,1,2,3,4..と連続して埋まった場合でn+1になるため

*3:というかライブラリ関数で難しそうだったので避けた