特定の値から出発して演算を繰り返し値の並びを出力する unfold 。 そういえば Ruby に unfold ってないんだっけ？ というのが発端。
unfold とは
早い話が fold の逆です。
Elixir では Stream.unfold/2 が定義されています。
# 1 から始めて、前の値に 1 を加える Stream.unfold(1, fn x -> {x, x + 1} end) |> Enum.take(10) #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# 1 から始めて、前の値を 2 倍にする Stream.unfold(1, fn x -> {x, x * 2} end) |> Enum.take(10) #=> [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
# フィボナッチ数列 Stream.unfold({1, 1}, fn {n1, n2} -> {n1, {n2, n1 + n2}} end) |> Enum.take(10) #=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
Stream.unfold/2 自体は終端を定義しません。
Enum でなく Stream で定義されているのもそのためです。
Enum.take/2 などで必要な分を取り出す必要があります。
Ruby で unfold を書く（終端を条件で判断するばあい）
最初に思いつくのは、繰り返しの中で yield を使い、結果を集める方法。
しかし無制限にいつまでも繰り返すわけにはいかないので、終了条件を織り込まないとなりません。
実装するとこんな感じ。
def unfold(x) result = [] loop do y, x = yield x break if x.nil? result.push y end result end
# 1 から始めて、10 以下の範囲で前の値に 1 を加える unfold(1) do |x| [x, x + 1] if x <= 10 end #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# 1 から始めて、512 以下の範囲で前の値を 2 倍にする unfold(1) do |x| [x, x * 2] if x <= 512 end #=> [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
# 55 以下の値のフィボナッチ数列 unfold([1, 1]) do |n1, n2| [n1, [n2, n1 + n2]] if n1 <= 55 end #=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
Ruby で unfold を書く
しかし冒頭の Stream.unfold/2 の例のように決められた個数の要素を取り出すようなばあいにはこれでは不便です。
そこで「Ruby unfold」で検索すると、簡単にヒットするのがこちらのコード。
実のところ、これがほぼ正解っぽいです。
Enumerator.new のブロックの引数として渡される Enumerator::Yielder オブジェクトの存在も初めて知りました。
def unfold(x) Enumerator.new do |yielder| loop do y, x = yield x yielder << y end end end
unfold(1) { |x| [x, x + 1] }.take(10) #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
unfold(1) { |x| [x, x * 2] }.take(10) #=> [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
unfold([1, 1]) { |x, y| [x, [y, x + y]] }.take(10) #=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
この実装でしたら最初に書いた終端を条件で判断するケースにも対応できます。
unfold([1, 1]) { |x, y| [x, [y, x + y]] }.take_while { _1 < 100 } #=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
Elixir の Stream.unfold/2 も Enum.take_while/2 を使って同じように書けます。
Stream.unfold({1, 1}, fn {n1, n2} -> {n1, {n2, n1 + n2}} end) |> Enum.take_while(& &1 < 100) #=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
モジュールにしてみた
繰り返し利用できるようにモジュールを定義してみました。 が、今ひとつ。 定義の仕方がうまくないというのもありますが、初期値と操作の結びつきが強いので、任意の操作を受け取れるようにしても使い勝手がよくないということなのかもしれません。
module Unfoldable def unfold x = self Enumerator.new do |yielder| loop do y, x = yield x yielder << y end end end end
Integer.include(Unfoldable) 1.unfold { |x| [x, x + 1] }.take(10) #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
a = [1, 1] a.extend(Unfoldable) a.unfold { |n1, n2| [n1, [n2, n1 + n2]] }.take(10) #=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
