Elixir のリスト内包表記でクイックソート

Elixir にはリスト内包表記という記法があり、これを使うとリストに対して

• 任意の条件でフィルタリング
• 別の値へのマッピング

というよくある操作を簡潔に記述できる。

• http://elixir-ja.sena-net.works/getting_started/18.html

例

iex> for n <- 1..10, rem(n, 2) == 0, do: n * n
[4, 16, 36, 64, 100]

これは 1 〜 10 の値のうち偶数の値の自乗を求めている。このように Elixir ではリスト内包表記は for で始まる式になるようだ。

このとき

• n <- [1 .. 10] が生成器 (generator) : 入力になるリストの指定
• rem(n, 2) == 0 がフィルタ : リストに対してこの条件でフィルタリングする
• n * n が構築子 (constructor) : 結果に対して作用して出力を作る

というルールになっている。

生成器でリストを作って、場合に応じてフィルタし、構築子で戻り値を組み立てる。

クイックソート

プログラミング Erlang に載っている Quick Sort をリスト内包表記で書く例、これを Elixir で書くと以下のようになる。

defmodule QuickSort do
  def qsort([pivot|t]) do
    qsort(for x <- t, x < pivot, do: x)
    ++ [pivot] ++
    qsort(for x <- t, x >= pivot, do: x)
  end

  def qsort([]), do: []
end

IO.inspect QuickSort.qsort([23, 6, 2, 9 , 27, 400, 78, 45, 61, 82, 14])

実行結果は

$ elixir quick_sort.ex
[2, 6, 9, 14, 23, 27, 45, 61, 78, 82, 400]

となった。ただしく動いている。

仮引数のパターンマッチで pivot を取り出すことができるし、リスト内包表記でフィルタが簡単に書けて簡潔に記述できる。

まあ、この場合構築子は使ってないので for x <- t, x < pivot, do: x は

Enum.filter(t, fn(x) -> x < pivot end)

でも構わないのだが。

ピタゴラス数

よりリスト内包表記をそれっぽく使った例は、同じく書籍からピタゴラス数を求める例。A² + B² = C² を満たす A, B, C の組を求める。

これを Elixir で書くと

defmodule Pythag do
  def pythag(n) do
    for a <- 1..n, 
        b <- 1..n, 
        c <- 1..n, 
        a + b + c <= n, a*a + b*b === c*c, do: {a, b, c}
  end
end

IO.inspect Pythag.pythag(16)
IO.inspect Pythag.pythag(30)

と書けて結果は

$ elixir pythag.ex
[{3, 4, 5}, {4, 3, 5}]
[{3, 4, 5}, {4, 3, 5}, {5, 12, 13}, {6, 8, 10}, {8, 6, 10}, {12, 5, 13}]

となる。生成器やフィルタに複数の式が書けることで簡潔に記述できる。

こんなところに書いてないで Web+DB の原稿書けや、という声が聞こえる･･･