はじめてなElixir(6) 線形じゃない空間での遅延評価

一直線じゃない構造で、かつ無限な空間での遅延評価を試します。結果論ですが、パターンマッチをうまく使う機会にもなりました。

脱線が止まりません。はじめてなElixir(5)でやめようと思ってたんですが。

線形じゃない空間

Elixir （でも他の遅延評価を持つ言語でも）無限xx に遅延評価を行うことができます。このxxのところはリスト、線形な構造です。始まりがあってずーっと後に続いていく構造です。これは自然数同様ですね。で、まっすぐじゃない場合もあるだろうとうことで、今回は2次元空間での遅延評価をやってみます。

対象とする2次元空間

線形じゃない無限な構造と言ってもいろいろあるでしょうが、ここでは2次元で行きます。
はじめてなElixir(4)で有理数をやったので、有理数の空間でやってみます。

	1	2	3	4	...
1	1/1	2/1	3/1	4/1	...
2	1/2	2/2	3/2	4/2	...
3	1/3	2/3	3/3	4/3	...
4	1/4	2/4	3/4	4/4	...
...	...	...	...	...	...

ってな表があるとして、これを全部くまなく覆うように旅をすると、こういう列ができたりします。

$\frac{1}{1}$ $\rightarrow$ $\frac{1}{2}$ $\rightarrow$ $\frac{2}{1}$ $\rightarrow$ $\frac{1}{3}$ $\rightarrow$ $\frac{2}{2}$ $\rightarrow$ $\frac{3}{1}$ $\rightarrow$ $\frac{1}{4}$ $\rightarrow$ $\frac{2}{3}$ $\rightarrow$ $\frac{3}{2}$ $\rightarrow$ $\frac{4}{1}$ $\rightarrow\ldots$

2次元空間だけど1次元空間にマップできます。どんな分数でもこの列のどこかに出てきます（正に限るけど）。

対角ルートをなぞる

これを Elixir で表現してみましょう。一通りなぞれることが分かれば、こういう x-y な無限空間に対して遅延評価による関数適用が一定可能であるということが言えると思います。

defmodule Rational do
  def stream do
    Stream.unfold({1, 1}, fn({s, r}) -> {{s, r}, succ({s, r})} end)
  end

  def succ({n, 1}) do {1,   n+1} end
  def succ({n, d}) do {n+1, d-1} end
end

わーい！ ついに左辺でパターンマッチできたぞ。イイねぇ。
分数は2要素のタプルで左が分子・右が分母で表してます。これを評価してみましょう。

iex(13)> Rational.genstream |> Enum.take(10)
[{1, 1}, {1, 2}, {2, 1}, {1, 3}, {2, 2}, {3, 1}, {1, 4}, {2, 3}, {3, 2}, {4, 1}]
iex(14)> 

とまあ難なくできちゃいました。
ただこれ、2/2 とか 3/3 とか表現が違えど同じ値の分数が何回も出てきちゃうんですね。これを取り除きましょう。

エラトステネスの篩

まずは準備をします。篩は「ふるい」ですよ。難しい漢字です。なんとか読めても書くことができない。英語なら sieve ですが、filter とか screen とかより目が細かい感じでしょうか。参考になるページ
無限リストによるエラトステネスのふるい
というのがあったので拝借します。若干古い記事ですがそのままで 1.7.3 で動きました。

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

  def primestream() do
    Stream.iterate(2, &(&1+1)) |> Eratosthenes.sieve
  end
end

すごいですね、これ。いきなり書けと言われても今の私には無理ですわ。要は、2を先頭とする昇順の正整数列が流れ込んできたら「先頭要素の倍数にならないようなフィルタをかける」… ってフィルタを前の要素から全部の値に対して用意するというものです。激しい…

重複する要素を取り除く（考え過ぎ版）

さて、これを参考に重複する要素を取り除くプログラムを作ります。要は列の後に出てくる分数のうち、約分して同じになるのを取っちゃえば良いです。

defmodule Rational do
  require Integer

  def sieve(seq) do
    Stream.unfold(seq, fn(s) ->
      head = Enum.at(s, 0)
      tail = Stream.filter(s, fn(r) -> head != Rational.rof(r) end)
      {head, tail}
    end)
  end

  def rof({n, d}) do
    {Kernel.div(n, Integer.gcd(n, d)), Kernel.div(d, Integer.gcd(n, d))}
  end

  def genstream() do
    Stream.unfold({1, 1}, fn({s, r}) -> {{s, r}, succ({s, r})} end)
  end

  def succ({n, 1}) do {1,   n+1} end
  def succ({n, d}) do {n+1, d-1} end
end

はじめてなElixir(4)で使った約分の関数 rof 関数をここでも使います。
tail = Stream.filter(s, fn(r) -> head != Rational.rof(r) end)
がキモで、今ある列の全部の要素で約分して先頭要素と同じにならないものを選んでます。

iex(7)> Rational.genstream |> Rational.sieve |> Enum.take(0) 
[]
iex(8)> Rational.genstream |> Rational.sieve |> Enum.take(1)
[{1, 1}]
iex(9)> Rational.genstream |> Rational.sieve |> Enum.take(5)
[{1, 1}, {1, 2}, {2, 1}, {1, 3}, {3, 1}]
iex(10)> Rational.genstream |> Rational.sieve |> Enum.take(10)
[{1, 1}, {1, 2}, {2, 1}, {1, 3}, {3, 1}, {1, 4}, {2, 3}, {3, 2}, {4, 1}, {1, 5}]

となって 2/2 が取り除かれてるのが分かります。でも先頭10個だとそれだけですね。もう少し多く拾ってみましょうか。

iex(19)> Rational.genstream |> Enum.take(20)
iex(20)> Rational.genstream |> Enum.take(20) |> Enum.drop(10)
[{1, 5}, {2, 4}, {3, 3}, {4, 2}, {5, 1}, {1, 6}, {2, 5}, {3, 4}, {4, 3}, {5, 2}]
iex(22)> Rational.genstream |> Rational.sieve |> Enum.take(20) |> Enum.drop(10)
[{5, 1}, {1, 6}, {2, 5}, {3, 4}, {4, 3}, {5, 2}, {6, 1}, {1, 7}, {3, 5}, {5, 3}]

篩を入れないときにあった 2/4 3/3 4/2 が篩を入れることでなくなってしまってるのが確認できます。

重複する要素を取り除く（普通こうだよね版）

と書いたところでなんだか複雑だなぁと思えてきました。取り除かれていく分数は以前に出てきた分数と同じ… ってことはそもそも約分できるような分数ということですね。以前に出てきた分数と比較なんかしなくても、その要素単体でチェックできるということに気づきました。ということは Stream.filter でできそうです。

defmodule Rational do
  require Integer

  def sieve(s) do
    Stream.filter(s, fn({n, d}) -> Integer.gcd(n, d) == 1 end)
  end

  def genstream() do
    Stream.unfold({1, 1}, fn({s, r}) -> {{s, r}, succ({s, r})} end)
  end

  def succ({n, 1}) do {1,   n+1} end
  def succ({n, d}) do {n+1, d-1} end
end

と大変シンプルにできました。エラトステネスさんはどこに行っちゃったんでしょうか。試しに動かしてみます。

iex(37)> Rational.genstream |> Rational.sieve |> Enum.take(0) 
[]
iex(38)> Rational.genstream |> Rational.sieve |> Enum.take(1)
[{1, 1}]
iex(39)> Rational.genstream |> Rational.sieve |> Enum.take(5)
[{1, 1}, {1, 2}, {2, 1}, {1, 3}, {3, 1}]
iex(40)> Rational.genstream |> Rational.sieve |> Enum.take(10)
[{1, 1}, {1, 2}, {2, 1}, {1, 3}, {3, 1}, {1, 4}, {2, 3}, {3, 2}, {4, 1}, {1, 5}]

はいちゃんと動きましたね。もう10個を見てみましょう。

iex(41)> Rational.genstream |> Rational.sieve |> Enum.take(20) |> Enum.drop(10)
[{5, 1}, {1, 6}, {2, 5}, {3, 4}, {4, 3}, {5, 2}, {6, 1}, {1, 7}, {3, 5}, {5, 3}]
iex(42)> Rational.genstream |> Rational.sieve |> Enum.take(20) |> Enum.take(-10) 
[{5, 1}, {1, 6}, {2, 5}, {3, 4}, {4, 3}, {5, 2}, {6, 1}, {1, 7}, {3, 5}, {5, 3}]
iex(43)> 

余談ですが、上のように Enum.drop(n) は Enum.take(-n) と同じでした。（n > 0 のときに限ります）

参考文献

無限リストによるエラトステネスのふるい
はじめてなElixir(3) Stream で遊んでみる
はじめてなElixir(4) 有理数モジュールをつくってみる
Elixir v1.7.3