無限ストリーム

Ruby

無限ストリーム？遅延ストリーム？のどっちなんだろ？gaucheのリファレンスマニュアルを見ながら実装。
これを使えばrubyでも簡単にSICP 3.5章の問題が解ける！かも。
cycleが解りづらい。構文を定義できないから仕方ないのだけれど、LazyStream::Cons.newの第二引数に必ずProcオブジェクトを渡さなければいけないのはきれいじゃない。

ソース

  • lazyevaluation.rb
module LazyEvaluation
  class Promise
    def initialize(expression=Proc.new)
      @expression = expression
      @is_already_run = false
      @result = nil
    end
    attr_reader :expression
    def call
      if not @is_already_run
        @result = @expression.call
        @is_already_run = true
      end
      @result
    end
    alias_method :force, :call
  end

  module_function
  def delay(expression=Proc.new)
    Promise.new(expression)
  end

  def lazy(expression=Proc.new)
    if expression.kind_of? Promise
      expression
    else
      Promise.new(expression)
    end
  end

  def force(promise)
    promise.call
  end

  def promise?(obj)
    obj.kind_of? Promise
  end
end
  • lazystream.rb
require 'lazyevaluation'

module LazyStream

  class Cons
    def initialize(car, cdr=Proc.new)
      @car = car
      @cdr = LazyEvaluation::Promise.new(cdr)
    end

    attr_reader :car
    def cdr
      @cdr.call
    end

    def nil?
      self == Nil
    end

    def [](n)
      curr = self
      loop do
        break nil if curr.nil?
        break curr.car if n == 0
        curr = curr.cdr
        n = n - 1
      end
    end

    def each(block=Proc.new)
      curr = self
      loop do
        break self if curr.nil?
        block.call curr.car
        curr = curr.cdr
      end
    end

    def map(block=Proc.new)
      Cons.new block.call(self.car), lambda {|kdr|
        lambda {
          return Nil if kdr.nil?
          kdr.map(block)
        }
      }.call(self.cdr)
    end
    alias_method :collect, :map

    def filter(pred_p=Proc.new)
      curr = self
      loop do
        break Nil if curr.nil?
        break Cons.new(curr.car, lambda {|kdr|
          lambda {
            return nil if kdr.nil?
            kdr.filter(pred_p)
          }
        }.call(curr.cdr)) if pred_p.call(curr.car)
        curr = curr.cdr
      end
    end

    def take(n)
      curr = self
      array = Array.new
      loop do
        break array if curr.nil?
        break array if n == 0
        array << curr.car
        curr = curr.cdr
        n = n - 1
      end      
    end

    def to_a
      curr = self
      array = Array.new
      loop do
        break array if curr.nil?
        array << curr.car
        curr = curr.cdr        
      end
    end

    def push(stream_or_array)
      stream = stream_or_array
      stream = LazyStream.stream(*stream) if stream.kind_of? Array
      return self if stream.nil?
      return stream if self.nil?
      Cons.new(self.car, lambda {
        if self.cdr.nil?
          stream
        else
          self.cdr.push stream
        end
      })
    end
    alias_method  :<<, :push

    def cycle
      Cons.new(self.car, lambda {|myself|
        kdr_proc = lambda {|kdr|
          lambda {
            return myself.cycle if kdr.nil?
            Cons.new kdr.car, kdr_proc.call(kdr.cdr)
          }
        }
        kdr_proc.call(self.cdr)
      }.call(self))
    end

    def +(stream_or_value)
      if LazyStream.stream?(stream_or_value)
        LazyStream.map(self, stream_or_value) {|a, b| a + b }
      else
        self.map {|n| n + stream_or_value }
      end
    end
    def -(stream_or_value)
      if LazyStream.stream?(stream_or_value)
        LazyStream.map(self, stream_or_value) {|a, b| a - b }
      else
        self.map {|n| n - stream_or_value }
      end
    end
    def *(stream_or_value)
      if LazyStream.stream?(stream_or_value)
        LazyStream.map(self, stream_or_value) {|a, b| a * b }
      else
        self.map {|n| n * stream_or_value }
      end
    end
  end

  Nil = Cons.new(nil, lambda { Nil })

  module_function
  def stream?(obj) obj.nil? or pair? obj end
  def pair?(obj) obj.kind_of? Cons end
  def nil?(obj) obj.kind_of? Cons and obj.nil? end
  def car(obj) obj.car end
  def cdr(obj) obj.cdr end
  def ref(stream, n) stream[n] end
  def take(stream, n) stream.take(n) end

  def stream(*objs)
    return Nil if (objs[0]).nil?
    Cons.new objs[0], lambda {
      objs = objs[1..-1]
      if objs[0].nil?
        Nil
      else
        self.stream(*objs)
      end
    }
  end
  def make_stream(n, init=false)
    return Nil if n == 0
    Cons.new init, lambda {self.make_stream(n-1, init)}
  end

  def map(*streams, &block)
    block = streams.pop if not block_given?
    kars=streams.map{|stream| stream.car}
    return Nil if kars.include? Nil
    Cons.new block.call(*kars), lambda {
      kdrs = streams.map{|stream| stream.cdr}
      self.map(*(kdrs << block))
    }
  end
  alias_method :collect, :map
  module_function :collect
end

使い方

> (ones = LazyStream::Cons.new(1, lambda { ones })).take 10
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
> LazyStream.make_stream(10, 12).collect do |n|
  n * n
end.filter do |n|
  n % 2 == 0
end.each{|n| p n}.to_a
144
144
144
144
144
144
144
144
144
144
[144, 144, 144, 144, 144, 144, 144, 144, 144, 144]
> LazyStream.make_stream(10, 100).take(5).to_a
[100, 100, 100, 100, 100]
> (LazyStream.make_stream(10, 100) << (1..10).to_a).to_a
[100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
> LazyStream.stream(*(1..10).to_a).cycle.take(25).to_a
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5]

修正

  • loopからの脱出をbreakに統一。loopはbreakするもの。
  • 四則演算を追加（三つだけだけど
  • LazyStream.mapを修正

追記

こんなすばらしいものが！！僕のはschemeにとらわれすぎだorz