Ruby で遅延ストリーム（コピペ）

お気楽Rubyプログラミング入門/番外編 遅延評価と遅延ストリーム
下はこのページのコードをまとめたもの（コピペ）。

lazystream.rb

#
# lazystream.rb : 遅延ストリーム
#
#                 Copyright (C) 2017 Makoto Hiroi
#

# 遅延評価
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

#
# 遅延ストリーム
#
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
  
  # 生成
  def LazyStream.iterate(a, &func)
    LazyStream.new(a) { iterate(func.call(a), &func) }
  end

  def LazyStream.tabulate(a = 0, &func)
    LazyStream.new(func.call(a)) { tabulate(a + 1, &func) }
  end
  
  def LazyStream.iota(n, m, stepno = 1)
    return @@NIL if n > m
    LazyStream.new(n) { iota(n + stepno, m) }
  end

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

  #
  # 基本操作
  #
  def first
    raise LazyStreamError, "Stream is empty" if empty?
    @item
  end

  def rest
    raise LazyStreamError, "Stream is empty" if empty?
    @next.force
  end

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

  def take(n)
    xs = self
    ys = []
    n.times {
      break if xs.empty?
      ys.push xs.first
      xs = xs.rest
    }
    ys
  end
  
  def drop(n)
    xs = self
    n.times {
      break if xs.empty?      
      xs = xs.rest
    }
    xs
  end

  def zip(xs)
    return @@NIL if empty? || xs.empty?
    LazyStream.new([first, xs.first]) { rest.zip(xs.rest) }
  end

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

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

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

  def each_cons(n)
    return @@NIL if empty?
    a = []
    xs = self
    n.times {
      return @@NIL if xs.empty?
      a.push xs.first
      xs = xs.rest
    }
    LazyStream.new(a) { rest.each_cons(n) }
  end

  def each_slice(n)
    return @@NIL if empty?
    a = []
    xs = self
    n.times {
      break if xs.empty?
      a.push xs.first
      xs = xs.rest
    }
    LazyStream.new(a) { xs.each_slice(n) }
  end

  # 併合
  def merge(xs)
    if empty?
      xs
    elsif xs.empty?
      self
    else
      if first <= xs.first
        LazyStream.new(first) { rest.merge(xs) }
      else
        LazyStream.new(xs.first) { merge(xs.rest) }
      end
    end
  end

  # 和集合
  def union(xs)
    if empty?
      xs
    elsif xs.empty?
      self
    else
      if first < xs.first
        LazyStream.new(first) { rest.union(xs) }
      elsif xs.first < first
        LazyStream.new(xs.first) { union(xs.rest) }
      else
        LazyStream.new(first) { rest.union(xs.rest) }
      end
    end
  end

  # 積集合
  def intersection(ys)
    xs = self
    loop {
      if xs.empty? || ys.empty?
        return @@NIL
      elsif xs.first == ys.first
        return LazyStream.new(xs.first) { xs.rest.intersection(ys.rest) }
      elsif xs.first < ys.first
        xs = xs.rest
      else
        ys = ys.rest
      end
    }
  end
  
  #
  # 高階関数
  #
  def map(&func)
    return @@NIL if empty?
    LazyStream.new(func.call(first)) { rest.map(&func) }
  end

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

  def zip_with(xs, &func)
    return @@NIL if empty? || xs.empty?
    LazyStream.new(func.call(first, xs.first)) {
      rest.zip_with(xs.rest, &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
    
  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
end

require_relative 'lazystream_lib'

自分による追加。
lazystream_lib.rb

class LazyStream
  def dig(n)
    LazyStream.new(first[n]) {rest.dig(n)}
  end
  
  def to_a
    xs = self
    ar = []
    until xs.empty?
      ar << xs.first
      xs = xs.rest
    end
    ar
  end
  
  def length
    return 0 if empty?
    1 + rest.length
  end
  
  def inspect
    return "//" if empty?
    first.inspect + " " + rest.inspect
  end
end

FizzBuzz

require_relative 'lazystream'

def change(n)
  return "FizzBuzz" if (n % 15).zero?
  return "Fizz"     if (n %  3).zero?
  return "Buzz"     if (n %  5).zero?
  n.to_s
end

p LazyStream.iota(1, 50).map {|x| change(x)}.to_a
#=>["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"]

あるいは

p LazyStream.iterate(1) {|x| x + 1}.map {|x| change(x)}.take(50)

あるいは

p LazyStream.tabulate(1) {|x| change(x)}.take(50)

フィボナッチ数列

def fibo(a, b)
  LazyStream.new(a) {fibo(b, a + b)}
end

fibos = fibo(1, 1)
result = []
20.times do
  result << fibos.first
  fibos = fibos.rest
end
p result
#=>[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

あるいは

fibos = LazyStream.iterate([1, 1]) {|a, b| [b, a + b]}
p fibos.dig(0).take(20)
#=>[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

あるいは

def add_stream(xs, ys)
  xs.zip_with(ys) {|x, y| x + y}
end

fibo = LazyStream.new(1) do
  LazyStream.new(1) {add_stream(fibo.rest, fibo)}
end

p fibo.take(20)
#=>[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

エラトステネスの篩

def sieve(xs)
  p = xs.first
  LazyStream.new(p) { sieve(xs.rest.filter {|x| x % p != 0}) }
end

ps = sieve(LazyStream.iterate(2) {|x| x + 1})
p ps.take(25)
#=>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

ニュートン-ラプソン法による平方根

なぜ関数プログラミングは重要か
「なぜ関数プログラミングは重要か」解読（Ruby） - Camera Obscura

a0 = 1.0
eps = 0.001

repeat = ->(n) { LazyStream.iterate(a0) {|x| (x + n / x) / 2} }

within = ->(ls) do
  a = ls.first
  b = ls.rest.first
  return b if (a - b).abs <= eps
  within[ls.rest]
end

p within[repeat[2.0]]    #=>1.4142135623746899

relative = ->(ls) do
  a = ls.first
  b = ls.rest.first
  return b if (a - b).abs <= eps * b.abs
  relative[ls.rest]
end

p relative[repeat[3.0]]  #=>1.7320508100147274

いろいろ

a = LazyStream.iota(1, 5)
b = LazyStream.iota(8, 12)
p a.length
p a.append(b)

p LazyStream.of([1, "2", :a])

def factorial(n)
  LazyStream.iota(1, n).reduce(1) {|r, i| r * i}
end

p factorial(10)

def dice
  LazyStream.tabulate {rand(1..6)}
end

p dice.take(20)

#=>
5
1 2 3 4 5 8 9 10 11 12 //
1 "2" :a //
3628800
[5, 1, 6, 5, 3, 1, 6, 4, 1, 6, 5, 5, 4, 2, 6, 2, 5, 4, 4, 2]