Delayed list in Ruby

class DCons
  include Enumerable

  UNDEF = Object.new.freeze

  class NILC
    include Enumerable

    def first(n = UNDEF)
      n.equal?(UNDEF) ? nil : self
    end

    def tail
      self
    end

    def drop(n)
      self
    end

    def nil?
      true
    end

    def each
    end

    def _try
      self
    end

    def empty?
      true
    end
  end
  NIL = NILC.new

  def initialize(first, tail = UNDEF, &calc)
    @first = first
    @tail = tail
    @calc = calc  if @tail.equal? UNDEF
  end

  def empty?
    false
  end

  def first(n = UNDEF)
    if n.equal?(UNDEF)
      @first
    else
      res = []
      list = self
      until list.nil? || n <= 0
        res << list.first
        list = list.tail
        n -= 1
      end
      res
    end
  end

  def take(n)
    first(n)
  end

  def tail
    if @tail.equal? UNDEF
      calc, @calc = @calc, nil
      @tail = calc ? calc.call : NIL
    else
      @tail
    end
  end

  def drop(n)
    list = self
    until list.nil? || n <= 0
      list = list.tail
      n -= 1
    end
    list
  end

  def each
    if block_given?
      list = self
      until list.nil?
        yield list.first
        list = list.tail
      end
    end
    self
  end

  def _try
    tail.nil? ? NIL : yield
  end

  def find_all(&filter)
    list = self
    list = list.tail  until filter.call(list.first)
    dcons(list.first){ list._try{ list.tail.find_all(&filter) } }
  end

  alias select find_all

  def map(&calc)
    dcons calc.call(first) do
      _try{ tail.map(&calc) }
    end
  end
  alias collect map

  def zip(*args)
    cars = args.map{|o| o.first}
    zipped = dcons [first, *cars] do
      _try {
        cdrs = args.map{|o| o.tail}
        tail.zip(*cdrs)
      }
    end
    if block_given?
      zipped.each Proc.new
      nil
    else
      zipped
    end
  end

  def zip_map(*args, &calc)
    zip(*args).map(&calc)
  end

  def _chunk_cons(cur_key, state, &block)
    list = self
    while true
      case cur_key
      when nil, :_separator
        return NIL if (list = list.tail).nil?
        cur_key = state ? yield(list.first, state) : yield(list.first)
      when :_alone
        return dcons([:_alone, [list.first]]){
          list._try{ list.tail._chunk_cons(key, state, &block) }
        }
      else
        break
      end
    end
    key = cur_key
    res = []
    until list.nil? || key != cur_key
      res << list.first
      unless (list = list.tail).nil?
        key = state ? yield(list.first, state) : yield(list.first)
      else
        return dcons([cur_key, res])
      end
    end
    dcons([cur_key, res]){
      list.nil? ? NIL : list._chunk_cons(key, state, &block)
    }
  end

  def chunk(initial_state = nil, &block)
    state = initial_state.dup  if initial_state
    _chunk_cons yield(first), state, &block
  end

  def drop_while
    list = self
    list = list.tail  while !list.nil? && yield(list.first)
    list
  end

  def take_while(&block)
    if yield(first)
      dcons(first){ _try{ tail.take_while(&block) } }
    else
      NIL
    end
  end

  def each_cons(n)
    if (v = take(n)).size < n
      return block_given? ? nil : NIL
    end
    cons = dcons(v){ tail.each_cons(n) }
    if block_given?
      cons.each{|args| yield args}
      nil
    else
      cons
    end
  end

  def each_slice(n)
    cons = dcons(take(n)){
      tl = drop(n)
      tl.nil? ? NIL : tl.each_slice(n)
    }
    if block_given?
      cons.each{|args| yield args}
      nil
    else
      cons
    end
  end
end

def dcons(first, *caars, &calc)
  unless caars.empty?
    DCons.new(first, dcons(*caars, &calc))
  else
    DCons.new(first, &calc)
  end
end

module Enumerable
  def tail
    puts "ENUM TAKE #{self.inspect}"
    drop(1)
  end
end

class Array
  def sum
    p self
    inject(0){|s, i| s + i}
  end
end

fib = dcons(0, 1){ fib.zip_map(fib.tail, &:sum) }
p fib.take(ARGV[0].to_i)
p fib.take(ARGV[0].to_i)
fib2 = fib.tail.tail.tail
fib = nil
p fib2.take(4)

p fib2.find{|i| i > 1e10}
p fib2.find_all(&:even?).take(10)

p fib2.chunk(&:even?).take(10)


ints = dcons(0){ ints.map{|i| i+1} }
p ints.take(10)
p ints.zip((100..105)).take(10)


p ints.chunk{|i| i % 3 == 2 ? nil : i / 3}.take(10)
p ints.chunk{|i| i % 3 == 1 ? nil : i / 3}.take(10)
p ints.chunk(""){|i| i % 3 == 1 ? nil : i / 3}.take(10)


pure = ints.drop(2)
pure = pure.find_all{|i|
  sqrt = Math.sqrt(i)
  pure.take_while{|j| j <= sqrt}.all?{|j| i % j != 0}
}
p pure.take_while{|i| i < 1000}.to_a


def sieve(stream)
  first = stream.first
  dcons(first){
    stream._try {
      sieve stream.tail.find_all{|v| v % first != 0}
    }
  }
end
pure1 = sieve(ints.drop(2))
p pure1.take_while{|i| i < 1000}.to_a

def timeit
  t = Time.now
  yield
  Time.now - t
end
puts timeit{ pure.take_while{|i| i < 5000}.to_a }
puts timeit{ pure1.take_while{|i| i < 5000}.to_a }


p pure.take_while{|i| i < 20}.each_cons(3).to_a
p pure.take_while{|i| i < 20}.each_slice(3).to_a