M.Hiroi's Home Page
http://www.geocities.jp/m_hiroi/

お気楽 Ruby プログラミング入門

番外編 遅延評価と遅延ストリーム

[ PrevPage | R u b y | NextPage ]

遅延評価

一般的なプログラミング言語の場合、関数を呼び出す前に引数が評価され、その結果が関数に渡されます。これを「正格 (strict) な評価」といいます。これに対し、引数や変数の値が必要になるまで評価を行わない方法もあります。具体的には、引数や変数を参照するときに評価が行われます。これを「遅延評価 (delayed evaluation または lazy evaluation)」といいます。

プログラミング言語では純粋な関数型言語である Haskell が遅延評価です。また、Scheme でも delay と force を使って遅延評価を行うことができます。そして、その評価結果は保存されることに注意してください。再度変数や引数を参照すると、保存されている値が返されます。

なお、値の保存 (キャッシング) をしないでよければ、クロージャを使って遅延評価を行うこともできます。Ruby はクロージャ (手続きオブジェクト) をサポートしているので、遅延評価を実装することは簡単です。今回は Ruby で遅延評価を行うクラス Delay を作ってみましょう。

●遅延評価の実装

Delay.new() は遅延評価を行う処理を手続きオブジェクトで受け取ります。実行はメソッド force() で行います。このとき、評価結果がインスタンスに保存されることに注意してください。本稿では、Delay のインスタンスを「遅延オブジェクト」と呼ぶことにします。再度 force() を実行すると、保存された値が返されます。

プログラムは次のようになります。

リスト : 遅延評価

class Delay
  def initialize(&func)
    @func = func
    @flag = false
    @value = false
  end

  def force
    unless @flag
      @value = @func.call
      @flag = true
    end
    @value
  end
end

遅延評価する処理はブロック引数 &func で受け取って変数 @func にセットします。@flag は false で初期化します。メソッド force() は最初に @flag をチェックします。偽の場合、@func はまだ評価されていません。@func.call() を実行して、その返り値を @value にセットし、@flag を true に書き換えます。@flag が true ならば @func は評価済みなので @value を返します。

簡単な使用例を示します。

irb> p = Delay.new {
irb> puts "oops!"
irb> 10 + 20
irb> }
=> #<Delay: ... @func=#<Proc: ... >, @flag=false, @value=false>
irb> p.force
oops!
=> 30
irb> p.force
=> 30

遅延オブジェクトを変数 p にセットします。このとき、手続きオブジェクトは実行されていません。p.force() を実行すると手続きオブジェクトが評価されるので、画面に oops! が表示されて計算結果の 30 が返されます。p.force() を再度実行すると、同じ式を再評価しないで @value に格納された値を返します。この場合 oops! は表示されません。

●たらいまわし関数

遅延評価の簡単な例題として「たらいまわし関数」を取り上げます。次のリストを見てください。

リスト : たらいまわし関数

def tarai(x, y, z)
  return y if x <= y
  tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y))
end

def tak(x, y, z)
  return z if x <= y
  tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y))
end

関数 tarai() と tak() は「たらいまわし関数」といって、再帰的に定義されています。これらの関数は、引数の与え方によっては実行に時間がかかるため、Lisp などのベンチマークに利用されることがあります。Common Lisp のプログラムは ぬえ 鵺 NUETAK Function にあります。

tarai() は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄先生によって考案されたそうです。そして、tak() は tarai() のバリエーションで、John Macarthy 先生によって作成されたそうです。たらいまわし関数が Lisp のベンチマークで使われていたことは知っていましたが、このような由緒ある関数だとは思ってもいませんでした。

それでは、さっそく実行してみましょう。実行環境は Lubuntu 16.04 on VirtualBox, Core i7-2670QM 2.20GHz です。

irb> require "benchmark"
=> true
irb> load "tarai.rb"
=> true
irb> Benchmark.realtime { tarai(12, 6, 0) }
=> 0.9319958629998837
irb> Benchmark.realtime { tak(18, 9, 0) }
=> 1.0928820149999865

このように、たらいまわし関数は引数の値が小さくても実行に時間がかかります。

●遅延評価による高速化

たらいまわし関数は遅延評価を使って高速化することができます。tarai() のプログラムを見てください。x <= y のときに y を返しますが、このとき引数 z の値は必要ありませんね。引数 z の値は x > y のときに計算するようにすれば、無駄な計算を省略することができます。ただし、tak() は遅延評価で高速化することはできません。ご注意くださいませ。

クラス Delay を使うと、たらいまわし関数は次のようになります。

リスト : Delay による遅延評価

def tarai_lazy(x, y, z)
  return y if x <= y
  tarai_lazy(tarai_lazy(x - 1, y, z),
             tarai_lazy(y - 1, z.force, Delay.new { x }),
             Delay.new { tarai_lazy(z.force - 1, x, Delay.new { y }) })
end

tarai_lazy() のプログラムを見てください。遅延評価したい処理を Delay に包んで引数 z に渡します。そして、x > y のときに引数 z を評価 (z.force()) します。すると、遅延オブジェクトが評価されて z の値を求めることができます。

たとえば、{ 0 } を Delay に渡す場合、z.force() とすると返り値は 0 になります。{ x } を渡せば、x に格納されている値が返されます。{ tarai_lazy( ... ) } を渡せば、関数 tarai_lazy() が実行されてその値が返されるわけです。

それでは実行してみましょう。

irb> Benchmark.realtime { tarai_lazy(18, 9, Delay.new {0}) }
=> 0.0005394669999532198
irb> Benchmark.realtime { tarai_lazy(180, 90, Delay.new {0}) }
=> 0.036651302999871405

tarai() の場合、遅延評価の効果はとても大きいですね。

●クロージャによる遅延評価

ところで、Delay を使わなくても、手続きオブジェクト (クロージャ) だけで遅延評価を行うことができます。次のリストを見てください。

リスト : クロージャによる遅延評価

def tarai_lazy1(x, y, z)
  return y if x <= y
  zz = z.call
  tarai_lazy1(tarai_lazy1(x - 1, y, z),
              tarai_lazy1(y - 1, zz, proc { x }),
              proc { tarai_lazy1(zz - 1, x, proc { y }) })
end
irb> Benchmark.realtime { tarai_lazy1(180, 90, proc {0}) }
=> 0.032123816999956034

遅延評価したい処理をクロージャに包んで引数 z に渡します。そして、x > y のときに引数 z の関数を呼び出します。すると、クロージャ内の処理が評価されて z の値を求めることができます。たとえば、proc {0} を z に渡す場合、z.call とすると返り値は 0 になります。proc {x} を渡せば、x に格納されている値が返されます。proc { tarai_lazy1( ... ) } を渡せば、tarai_lazy1() が実行されてその値が返されるわけです。ただし、クロージャでは評価結果を保存 (キャッシュ) できないことに注意してください。


遅延ストリーム

「ストリーム (stream)」はデータの流れを抽象化したデータ構造です。たとえば、ファイル入出力はストリームと考えることができます。また、配列や連結リストを使ってストリームを表すこともできます。ただし、単純な配列や連結リストでは有限個のデータの流れしか表すことができません。ところが、遅延評価を用いると擬似的に無限個のデータを表すことができるようになります。これを「遅延ストリーム」とか「遅延リスト」と呼びます。

Ruby の Enumerator や Enumerator::Lazy は遅延リストですが、メソッド next() は状態を書き換えることで動作するので immutable ではありません。また、実行結果もキャッシュしていません。前回作成したクラス Delay を使うと、完全ではありませんが関数型言語のような immutable な遅延ストリームを作ることができます。まあ、immutable な遅延ストリームを Ruby で使うことはほとんどないと思いますが、今回は Ruby のお勉強ということで、実際にプログラムを作ってみましょう。

●遅延ストリームの構造

遅延ストリームの基本的な考え方は、必要になったときに新しいデータを生成することです。このときに遅延評価を用います。具体的にはデータを生成するメソッドを用意し、それを遅延評価してストリームに格納しておきます。そして、必要になった時点で遅延評価しておいたメソッドを呼び出して値を求めればよいわけです。

今回作成する遅延ストリームはクラス名を LazyStream とします。プログラムは次のようになります。

リスト : 遅延ストリーム

class LazyStreamError < StandardError
end

class LazyStream
  def initialize(x, &func)
    @item = x
    @next = Delay.new &func
  end

  def inspect                                                             
    "(" + @item.to_s + ", ?)"                                             
  end                              

  # 終端
  @@NIL = LazyStream.new(nil) { nil }

  def empty?
    self == @@NIL
  end
  
  def LazyStream.empty
    @@NIL
  end

  # メソッドの定義
  ・・・省略・・・
end

LazyStreamError はエラーを表すクラスです。LazyStream の変数 @item に先頭の要素を格納し、@next に遅延ストリームを生成する遅延オブジェクトを格納します。これを force() することで、次の要素を格納した遅延ストリームを生成します。クラス変数 @@NIL は遅延ストリームの終端 (空の遅延ストリーム) を表します。クラスメソッド empty() は空の遅延ストリームを返し、メソッド empty?() は遅延ストリームが空であれば真を返します。

次は遅延ストリームを操作する基本的なメソッドを定義します。

リスト : 遅延ストリームの基本的な操作メソッド

  # 先頭要素を取り出す
  def first
    raise LazyStreamError, "Stream is empty" if empty?
    @item
  end

  # 先頭要素を取り除く
  def rest
    raise LazyStreamError, "Stream is empty" if empty?
    @next.force
  end

メソッド first() は遅延ストリームから要素を取り出して返します。メソッド rest() は遅延ストリームの変数 @next を force() して、次の要素を格納した遅延ストリームを生成します。つまり、LazyStream.new(), first(), rest() は Lisp / Scheme でいうリスト操作関数 cons, car, cdr に対応します。

簡単な実行例を示します。

irb> a = LazyStream.new(1) { LazyStream.empty }
=> (1, ?)
irb> b = LazyStream.new(2) { a }
=> (2, ?)
irb> c = LazyStream.new(3) { b }
=> (3, ?)
irb> c.first
=> 3
irb> c.rest.first
=> 2
irb> c.rest.rest.first
=> 1
irb> c.rest.rest.rest.empty?
=> true

●遅延ストリームの生成

次は、遅延ストリームを生成するクラスメソッドを作りましょう。たとえば、n 以上 m 以下の整数列を生成する遅延ストリームは次のようにプログラムすることができます。

リスト : 整数列を生成する遅延ストリーム

  def LazyStream.iota(n, m, stepno = 1)
    return @@NIL if n > m
    LazyStream.new(n) { iota(n + stepno, m) }
  end

クラスメソッド iota() は遅延ストリームを生成して返します。new() の引数が現時点でのデータになり、ブロックの中で iota() を呼び出します。rest() を実行すると、遅延オブジェクトに格納された手続きオブジェクトが評価され、その本体である iota() が実行されて次のデータを格納した遅延ストリームが返されます。その遅延ストリームに対してさらに rest() を実行すると、その次のデータを取得することができます。

簡単な例を示しましょう。

irb> xs = LazyStream.iota(1, 10)
=> (1, ?)
irb> xs.first
=> 1
irb> xs.rest.first
=> 2
irb> xs.rest.rest.first
=> 3
irb> xs1 = xs
=> (1, ?)
irb> 10.times {
irb> print xs1.first, " "
irb> xs1 = xs.rest
irb> }
1 2 3 4 5 6 7 8 9 10 => 10
irb> xs.first
=> 1
irb> xs.rest.first
=> 2

遅延ストリーム xs に rest() を適用することで、次々とデータを生成することができます。また、ループの中で変数 xs1 の値を書き換えれば、遅延ストリームの要素を順番に取り出していくことができます。このとき、遅延ストリーム自体の値は書き換えられていないことに注意してください。xs の値を書き換えない限り、xs.first の値は 1 で、xs.rest.first の値は 2 のままです。

●無限ストリームの生成

次は無限ストリームを生成するクラスメソッドを作りましょう。次のリストを見てください。

リスト : 無限ストリームの生成

  // 前項にメソッドを適用して次項を生成する
  def LazyStream.iterate(a, &func)
    LazyStream.new(a) { iterate(func.call(a), &func) }
  end

  // a から始まる整数列に関数 func を適用する
  def LazyStream.tabulate(a = 0, &func)
    LazyStream.new(func.call(a)) { tabulate(a + 1, &func) }
  end

メソッド iterate() は、第 1 引数に初項を指定して、第 2 引数のメソッドで前項から次項を生成します。これは new() の引数に a を渡して、ブロックの中で iterate() の第 1 引数に func.call(a) の返り値をセットするだけです。これで、引数 a の値から次項の値を求めることができます。メソッド tabulate() は引数 a から始まる整数列に関数 func を適用し、その結果を格納する遅延ストリームを返します。

簡単な実行例を示します。

irb> xs = LazyStream.iterate(1) {|x| x + 1}
=> (1, ?)
irb> xs.first
=> 1
irb> xs.rest.first
=> 2
irb> xs.rest.rest.first
=> 3
irb> ys = LazyStream.tabulate(1) {|x| x * x}
=> (1, ?)
irb> ys.first
=> 1
irb> ys.rest.first
=> 4
irb> ys.rest.rest.first
=> 9

もう一つ、簡単な例を示しましょう。フィボナッチ数列を生成する遅延ストリームを作ります。

irb> def fibo(a, b)
irb> LazyStream.new(a) { fibo(b, a + b) }
irb> end
=> :fibo
irb> fibos = fibo(0, 1)
=> (0, ?)
irb> 20.times {
irb> print fibos.first, " "
irb> fibos = fibos.rest
irb> }
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 => 20

関数 fibo() の引数 a がフィボナッチ数列の最初の項で、b が次の項です。したがって、ブロックの中に fibo(b, a + b) を格納しておけば、rest() を実行することでフィボナッチ数列を生成することができます。

また、次のように iterate() を使ってもフィボナッチ数列を生成することができます。

irb> fibos = LazyStream.iterate([0, 1]){|x, y| [y, x + y]}
=> ([0, 1], ?)
irb> 20.times {
irb> print fibos.first, " "
irb> fibos = fibos.rest
irb> }
[0, 1] [1, 1] [1, 2] [2, 3] [3, 5] [5, 8] [8, 13] [13, 21] [21, 34] [34, 55] [55, 89] 
[89, 144] [144, 233] [233, 377] [377, 610] [610, 987] [987, 1597] [1597, 2584] 
[2584, 4181] [4181, 6765] =>20

●遅延ストリームの操作メソッド

次は遅延ストリームを操作するメソッドを作りましょう。最初は n 番目の要素を求めるメソッド get() です。

リスト : n 番目の要素を求める

  def get(n)
    xs = self
    n.times {
      xs = xs.rest
    }
    xs.first
  end

get() は rest() を n 回繰り返して n 番目の要素を求めるだけです。

遅延ストリームから n 個の要素を取り出して配列に格納して返すメソッド take() と、先頭から n 個の要素を取り除くメソッド drop() も同様にプログラムすることができます。

リスト : 要素を n 個取り出して配列に格納して返す

  def take(n)
    xs = self
    ys = []
    n.times {
      break if xs.empty?
      ys.push xs.first
      xs = xs.rest
    }
    ys
  end
リスト : 先頭から n 個要素を取り除く

  def drop(n)
    xs = self
    n.times {
      break if xs.empty?
      xs = xs.rest
    }
    xs
  end

take() は times() で first() と rest() を n 回繰り返し、要素を配列に格納して返します。drop() は rest() を n 回繰り返すだけです。

簡単な実行例を示しましょう。

irb> fibos = fibo(0, 1)
=> (0, ?)
irb> 20.times {|x| print fibos.get(x), " "}
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 => 20
irb> fibos.take(20)
=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
irb> fibos.drop(30).take(10)
=> [832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986]

変数 fibos にフィボナッチ数列を生成する遅延ストリームをセットします。get() で順番に要素を 20 個取り出すと、その値はフィボナッチ数列になっていますね。take() を使うと取り出した要素を配列に格納することができます。drop() で 30 個の要素を取り除き、take() で 10 個の要素を取り出します。すると、その要素は 30 番目以降のフィボナッチ数列になります。

●遅延ストリームの連結

次は、2 つの遅延ストリームを受け取って 1 つの遅延ストリームを返すメソッドを考えてみましょう。一番簡単な操作は 2 つの遅延ストリームを連結することです。次のリストを見てください。

リスト : 遅延ストリームの連結

  def append(xs)
    return xs if empty?
    LazyStream.new(first) { rest.append(xs) }
  end

メソッド append() は自分 (self) と引数の遅延ストリーム xs を連結した遅延ストリームを返します。処理は簡単で、自分の要素を順番に取り出していき、空になったら xs を返すだけです。

次は 2 つの遅延ストリームの要素を交互に出力する遅延ストリームを作ります。次のリストを見てください。

リスト : 遅延ストリームの要素を交互に出力

  def interleave(xs)
    return xs if empty?
    LazyStream.new(first) { xs.interleave(rest) }
  end  

メソッド interleave() は、自分の要素を新しい遅延ストリームに格納したら、次は引数 xs の要素を新しい遅延ストリームに格納します。これはブロックで interleave() を呼び出すとき、xs に対して interleave() を呼び出して、その引数に rest() の返り値を渡すだけです。これで要素を交互に出力することができます。

簡単な実行例を示しましょう。

irb> xs = LazyStream.iota(1, 8)
=> (1, ?)
irb> ys = LazyStream.iota(11, 18)
=> (11, ?)
irb> xs.append(ys).take(16)
=> [1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14, 15, 16, 17, 18]
irb> ones = LazyStream.iterate(1, &:itself)
=> (1, ?)
irb> ones.take(16)
=> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
irb> twos = LazyStream.iterate(2, &:itself)
=> (2, ?)
irb> twos.take(16)
=> [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
irb> ones.append(twos).take(16)
=> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
irb> ones.interleave(twos).take(16)
=> [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]

append() の場合、無限ストリーム ones と twos を連結することはできません。ones の要素である 1 をずっと出力するだけです。ところが、interleave() ならば無限ストリームにも対応することができます。ones と twos を interleave() で連結すると、1 と 2 が交互に出力されます。

●高階関数

次は、遅延ストリーム用の高階関数を作りましょう。

リスト : 高階関数

  # マッピング
  def map(&func)
    return @@NIL if empty?
    LazyStream.new(func.call(first)) { rest.map(&func) }
  end

  # フィルター
  def filter(&func)
    xs = self
    while !xs.empty?
      if func.call xs.first
        return LazyStream.new(xs.first) { xs.rest.filter(&func) }
      end
      xs = xs.rest
    end
    @@NIL
  end

  # 畳み込み
  def reduce(a, &func)
    xs = self
    while !xs.empty?
      a = func.call a, xs.first
      xs = xs.rest
    end
    a
  end

  # 巡回
  def each(&func)
    xs = self
    while !xs.empty?
      func.call xs.first
      xs = xs.rest
    end
  end

map() は遅延ストリームの要素にメソッド func を適用し、その返り値を新しい遅延ストリームに格納して返します。filter() はメソッド func が真を返す要素だけを新しい遅延ストリームに格納して返します。

reduce() は遅延ストリームに対して畳み込みを行います。each() は遅延ストリームの要素にメソッド func を適用します。無限ストリームの場合、これらのメソッドは処理が終了しないので注意してください。

簡単な実行例を示しましょう。

irb> xs = LazyStream.iota(1, 20)
=> (1, ?)
irb> xs.map{|x| x * x}.each{|x| print x, " "}
1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 => nil
irb> xs.filter{|x| x % 2 == 0}.each{|x| print x, " "}
2 4 6 8 10 12 14 16 18 20 => nil
irb> xs.reduce(0){|a, b| a + b}
=> 210

変数 xs に 1 から 20 までの整数列を生成する遅延ストリームをセットします。map() にブロック {|x| x * x} を渡すと、要素を 2 乗した遅延ストリームを生成することができます。filter() にブロック {|x| x % 2 == 0} を渡すと、偶数の要素を取り出すことができます。これらの遅延ストリームに each() を適用すると、要素を順番に取り出して出力することができます。xs は有限個の遅延ストリームなので畳み込みを行うことができます。reduce() で要素の合計値を求めると 210 になります。

また、次のように FizzBuzz 問題も簡単に解くことができます。

irb> def change(n)
irb> return "FizzBuzz" if n % 15 == 0
irb> return "Fizz" if n % 3 == 0
irb> return "Buzz" if n % 5 == 0
irb> n.to_s
irb> end
=> :change
irb> LazyStream.iota(1, 100).map{|x| change(x)}.take(100)
=> ["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", 
"13", "14", "FizzBuzz", "16", "17", "Fizz", "19", "Buzz", "Fizz", "22", "23", "Fizz", 
"Buzz", "26", "Fizz", "28", "29", "FizzBuzz", "31", "32", "Fizz", "34", "Buzz", 
"Fizz", "37", "38", "Fizz", "Buzz", "41", "Fizz", "43", "44", "FizzBuzz", "46", "47", 
"Fizz", "49", "Buzz", "Fizz", "52", "53", "Fizz", "Buzz", "56", "Fizz", "58", "59", 
"FizzBuzz", "61", "62", "Fizz", "64", "Buzz", "Fizz", "67", "68", "Fizz", "Buzz", 
"71", "Fizz", "73", "74", "FizzBuzz", "76", "77", "Fizz", "79", "Buzz", "Fizz", "82", 
"83", "Fizz", "Buzz", "86", "Fizz", "88", "89", "FizzBuzz", "91", "92", "Fizz", "94", 
"Buzz", "Fizz", "97", "98", "Fizz", "Buzz"]

●遅延ストリームへの変換

次は配列を遅延ストリームに変換するクラスメソッド of() を作ります。

リスト : 配列を遅延ストリームに変換

  def LazyStream.of(xs, n = 0)
    return @@NIL if xs.size == n
    LazyStream.new(xs[n]) { of(xs, n + 1) }
  end

of() は配列 xs の先頭から要素を順番に取り出して、遅延ストリームに格納して返すだけです。簡単な実行例を示します。

irb> xs = LazyStream.of([1,2,3,4,5,6,7,8])
=> (1, ?)
irb> xs.each{|x| print x, " "}
1 2 3 4 5 6 7 8 => nil
irb> ys = LazyStream.of(["foo", "bar", "baz", "oops"])
=> (foo, ?)
irb> ys.each{|x| print x, " "}
foo bar baz oops => nil

●flat_map()

次は高階関数 flat_map() を作りましょう。このとき、次のように append() を使って flat_map() を定義すると問題が発生します。

リスト : flat_map() の定義 (間違い)

  def flat_map_bad(&func)
    return @@NIL if empty?
    func.call(first).append(rest.flat_map_bad(&func))
  end

Ruby のメソッドは正格評価なので、append() を実行する前に引数が評価されます。つまり、flat_map_bad() の評価は遅延されるのではなく、遅延ストリームが空になるまで flat_map_bad() が再帰呼び出しされるのです。これでは無限ストリームに対応することができません。

そこで、引数を遅延評価するメソッド lazy_append() を作ることにします。プログラムは次のようになります。

リスト : lazy_append() と flat_map()

  def lazy_append(ys)
    return ys.force if empty?
    LazyStream.new(first) { rest.lazy_append(ys) }
  end

  def flat_map(&func)
    return @@NIL if empty?
    func.call(first).lazy_append(Delay.new { rest.flat_map(&func) })
  end

lazy_append() は append() とほぼ同じですが、遅延ストリームが空になったら遅延オブジェクト ys を force() で評価するところが異なります。flat_map() では、appned() のかわりに lazy_append() を呼び出します。このとき、Delay.new() で生成した遅延オブジェクトを引数に渡します。

それでは実行してみましょう。

irb> xs = LazyStream.tabulate(1, &:itself)
=> (1, ?)
irb> xs.flat_map{|x| LazyStream.of(Array.new(x){ x })}.take(55)
=> [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 
7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 
10, 10, 10]

xs は無限ストリームになりますが、flat_map() は正常に動作していますね。

●take_while() と drop_while()

次は、遅延ストリームの先頭から述語が真を返す要素を取り出す take_while() と要素を取り除く drop_while() を作ります。

リスト : take_while() と drop_while()

  def take_while(&func)
    xs = self
    ys = []
    while !xs.empty? && func.call(xs.first)
      ys.push xs.first
      xs = xs.rest
    end
    ys
  end

  def drop_while(&func)
    xs = self
    while !xs.empty? && func.call(xs.first)
      xs = xs.rest
    end
    xs
  end

どちらのメソッドも難しいところはないと思います。簡単な実行例を示しましょう。

irb> xs = LazyStream.iota(1, 20)
=> (1, ?)
irb> xs.take_while{|x| x < 10}
=> [1, 2, 3, 4, 5, 6, 7, 8, 9]
irb> xs.drop_while{|x| x < 10}.each{|x| print x, " "}
10 11 12 13 14 15 16 17 18 19 20 => nil

今回はここまでです。次回は遅延ストリームを使っていろいろなプログラムを作ってみましょう。

●参考文献

  1. "Structure and Interpretation of Computer Programs (SICP)" 3.5 Streams

初版 2011 年 5 月 14 日
改訂 2017 年 1 月 28 日

Copyright (C) 2011-2017 Makoto Hiroi
All rights reserved.

[ PrevPage | R u b y | NextPage ]