無限リストによるエラトステネスのふるい

Elixir では Stream モジュールを使って、遅延評価と無限リストを扱うことができるがそれによりエラトステネスのふるいを、Haskell と同じように無限リストを使った記述ができるか･･･というのが今回の試み。結果としては、カッとなれば、できる。

以下、Stream の解説も交えてお届けする。

Enumerable プロトコルと Enum および Stream

Elixir の Enum モジュールには map/2 や filter/2 や zip/2 など、コレクション操作に必要な関数が多数実装されている。以下はそのドキュメントの例である。Functions のところに Enum の関数が列挙されているのが分かる。

ちなみにこのドキュメント閲覧は Dash の画面。自分は主に iOS 開発のドキュメント閲覧によく使っているが、見ての通り Elixir のドキュメント参照にも便利。

Greedy な Enum

話を元に戻して、この Enum の関数が使える対象のコレクションは List や Map などのデータ型である。

iex(1)> [1,2,3,4,5] |> Enum.map &(&1 * &1)
[1, 4, 9, 16, 25]

iex(6)> %{:a => 1, :b => 2, :c => 3} |> Enum.map fn({k, v}) -> {k, v * v} end
[a: 1, b: 4, c: 9]

このように List や Map など異なるデータ構造に同じ関数を適用できる背景には、List や Map が Enumerable プロトコルを実装したデータ型であり、Enum の関数群は Enumerable プロトコルが実装されたそれらデータ型を対象にしているという前提がある。

例えば Enum のソースを見ると

defimpl Enumerable, for: List do
  def reduce(_,     {:halt, acc}, _fun),   do: {:halted, acc}
  def reduce(list,  {:suspend, acc}, fun), do: {:suspended, acc, &reduce(list, &1, fun)}
  def reduce([],    {:cont, acc}, _fun),   do: {:done, acc}
  def reduce([h|t], {:cont, acc}, fun),    do: reduce(t, fun.(h, acc), fun)

  def member?(_list, _value),
    do: {:error, __MODULE__}
  def count(_list),
    do: {:error, __MODULE__}
end

と、確かに List に対して Enumerable が defimpl されている。

Enum はリストを渡すと、リスト全件に対して処理をする。たとえ欲しいのはリストの先頭数件に対しての結果であっても、100件のリストに100回処理をするという Greedy (貪欲) な実装である。

Lazy な Stream

一方、Enumerable を実装したデータ型を対象としているのは Enum 以外に、Stream がある。Stream は Elixir における Lazy ･･･ つまり遅延評価のためのデータ型であり、Enumerable な値は何でも Stream に変換することができる。

例を見るのが早い。

iex> st = [1,2,3,4,5] |> Stream.map &(&1 * &1)
#Stream<[enum: [1, 2, 3, 4, 5],
 funs: [#Function<45.29647706/1 in Stream.map/2>]]>

Enumerable であるところの List [1,2,3,4,5] を Stream.map/2 に渡して、自乗する関数を適用している。しかしこの式を評価した時点では関数はまだ適用されておらず、返却されたのは Stream データ型の値である。

iex> st |> Enum.take(2)
[1, 4]

そしてその Stream な値を Enum.take/2 に渡す。この時点で初めて関数が適用される。このとき Stream は遅延評価であるから、リストは 5 要素あるが、自乗のための関数は Enum.take(2) が要求している先頭 2要素のみ、つまり5回ではなく2回しか適用されていない!

このように Stream は Enumerable な値を Stream に変換して、その Stream に対して Enumerable な操作を適用することができ、それは遅延評価となる。要するに、Enumerable で扱ってるものを遅延評価できたらなーと思ったら Stream を持ち出せば良い。

より分かりやすい例を示す。

iex> 1..10000000000 |> Stream.filter(&(rem(&1, 2) == 0)) |> Enum.take(2)
[2, 4]

Range もまた Enumerable で、Stream に変換できる。このように巨大な Range を作っても、Stream の遅延評価によって、&(rem(&1, 2) == 0) は Enum.take(2) が要求する 2回しか適用されない。万歳。

Stream についてより詳しくは [翻訳] Elixirのストリーム が詳しい。

Stream で無限リストを扱う

Stream は遅延評価であり、結果的に無限リストを扱う基盤になる。

Stream はストリームを作るコンストラクト関数と呼ばれる関数をいくつか持っている。例えば、与えた関数を繰り返し適用する Stream.iterate/2 を使うと無限のシーケンスを作ることができる。

iex> Stream.iterate(0, &(&1+1)) |> Enum.take(10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

生成されたのは無限リストであるが Enum.take(10) が遅延評価されて、計算は期待通り 10 回で停止する。

無限リストでエラストテネスのふるい

さて、この無限リストを使ってエラトステネスのふるいを実装しようじゃないか、というのが趣旨である。前置きが長かった。

エラトステネスのふるいのあらまし

エラトステネスのふるいは、素数を発見するためのアルゴリズム。Wikipedia の エラトステネスの篩 の項に詳しいが、簡単には以下のようなアルゴリズムである。

素数は「1　と 自分以外に正の約数を持たない数」であるが、数字を小さい順に 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ... と見て素数を発見していくのにある法則があるのに気づく。

• 2 は素数
• 3 は素数
• 4 は 2 の倍数だから素数ではない
• 5 は素数
• 6 は 2 の倍数だから素数ではない
• 7 は素数
• 8 は 2 の倍数だから素数ではない
• 9 は 3 の倍数だから素数ではない
• 10 は 2 の倍数だから素数ではない

とみていったとき、4 や 6 や 8 や 9 など素数でない数というのは、必ずそれ以前に発見された素数の倍数になっている。素数の定義上、当たり前の法則である。従って、リストから発見された素数の倍数にあたる数をどんどん排除していけば残る数はすべて素数になるはずだ。エラトステネスのふるいではこの性質を利用する。

つまり

1. 2 以上の整数のリストを小さい順から見ていく
2. このとき先頭の要素は必ず素数である
3. その素数である先頭要素の倍数を以降のリストから削除する
4. 先頭要素 (素数) を取り出し、脇に置く
5. 2 以降を繰り返す

とすると、素数のリストが得られるわけである。

具体的には以下のようになる。

• [2, 3, 4, 5, 6, 7, 8, 9, 10]
• 2 は素数。2 を脇に置いて、倍数の 4, 6, 8, ... を削除
• [3, 5, 7, 9]
• 3 は素数。3 を脇に置いて、倍数の 9, 12, 15 ... を削除
• [5, 7]
• 5 は素数...
• [7]
• 7 は素数...
• 脇に置かれた数は [2, 3, 5, 7] ですべて素数

良い感じである。

無限な整数のリストに対して実装

このとき、数の上限が分かっている、すなわち整数のリストが有限なら上記の手順を繰り返せばそのうちリストに素数だけになって (素数はリストの先頭から取り除かれていくから) リストは空になり計算は停止するのだが、そうでない場合というのを考えるとどうにも困る。

しかし、このエラトステネスの篩は、数の上限がわからなくとも、無限リストと遅延評価を前提とした処理系であれば非常に簡単に実装できる。

以下は Haskell による実装。

primes :: [Int]
primes = sieve [2..]

sieve :: [Int] -> [Int]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0 ]

[2..] が無限リストを生成していて、sieve 関数が "ふるい" に相当する。素数であるところの先頭要素 p で、残りのリストからその倍数をフィルタする･･･ということを再帰している。

結果 primes 関数では素数の無限リストが得られる。

> take 10 primes
[2,3,5,7,11,13,17,19,23,29]

take を適用してその先頭 10 件を取得することができる。計算は意図通り停止する。

Elixir の Stream でどう書くか?

これを Elixir の Stream でも実装できるか、試行錯誤した。結果できた。

defmodule Eratosthenes do
  def sieve (seq) do
    Stream.unfold(seq, fn (s) ->
      p    = s |> Enum.at(0)
      next = s |> Stream.filter(fn(x) -> rem(x, p) != 0 end)
      {p, next}
    end)
  end
end

Stream.iterate(2, &(&1+1)) |> Eratosthenes.sieve |> Enum.take(10) |> IO.inspect
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Haskell のように全ての計算が遅延評価されるわけではないので宣言的にすんなりとはいかなかったものの、Stream を使えば実装できた。以下ちょっと解説。

まず 2 から始まるシーケンスの無限リストは先にみたように Stream.iterate/2 を使えば生成することができる。

seq = Stream.iterate(2, &(&1+1))

そしてふるいの処理だが、Stream.unfold/2 を使うことによって実装できる。

Stream.unfold/2 は、初期値と関数を引数に取って、その関数の返値として {アキュムレータに積む値, 次の関数への引数} を返すと、アキュムレータに値を積みながら、与えられた引数に繰り返し関数を適用していく･･･という挙動をするストリームを返す。うーん、言葉で説明するとなんだか難しい。以下は Stream.unfold/2 によるフィボナッチ数列の実装で、これを見る方がわかりやすいかもしれない。

fibs = Stream.unfold({0,1}, fn {f1, f2} ->
  {f1, {f2, f1 + f2}}
end)

fibs |> Enum.take(10) |> IO.inspect
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

まあ、ようするにフィボナッチ数列みたいに再帰的に計算していって無限リストを生成するような、そういうときに使える関数。

この Stream.unfold/2 を使って、与えられた整数のリストから、先頭要素 (素数) の倍数をフィルタする･･･のを再帰的にやっていって無限リストを生成した･･･というのが上のエラトステネスのふるいの Elixir 実装である。

まとめ

• Enumerable なデータ型に対して使える Enum と Stream
• Enum は Greedy、Stream は Lazy
• Stream を使えば無限リストを扱える
• エラトステネスのふるいを Stream.unfold/2 を使って実装、素数の無限リストを計算することができた