module Hamster::List

def accessor(sequence)
  sequence.reverse.each_char.reduce(self) do |memo, char|
    case char
    when "a" then memo.head
    when "d" then memo.tail
    end
  end
end

def add(item)
  append(Hamster.list(item))
end

def append(other)
  Stream.new do
    next other if empty?
    Sequence.new(head, tail.append(other))
  end
end

def at(index)
  drop(index).head
end

def break(&block)
  return span unless block_given?
  span { |item| !yield(item) }
end

def chunk(number)
  Stream.new do
    next self if empty?
    first, remainder = split_at(number)
    Sequence.new(first, remainder.chunk(number))
  end
end

def clear
  EmptyList
end

def combinations(number)
  return Sequence.new(EmptyList) if number == 0
  Stream.new do
    next self if empty?
    tail.combinations(number - 1).map { |list| list.cons(head) }.append(tail.combinations(number))
  end
end

def cons(item)
  Sequence.new(item, self)
end

def cycle
  Stream.new do
    next self if empty?
    Sequence.new(head, tail.append(cycle))
  end
end

def drop(number)
  Stream.new do
    list = self
    while !list.empty? && number > 0
      number -= 1
      list = list.tail
    end
    list
  end
end

def drop_while(&block)
  return self unless block_given?
  Stream.new do
    list = self
    list = list.tail while !list.empty? && yield(list.head)
    list
  end
end

def dup
  self
end

def each
  return self unless block_given?
  list = self
  until list.empty?
    yield(list.head)
    list = list.tail
  end
end

def each_chunk(number, &block)
  chunk(number).each(&block)
end

def elem_index(object)
  find_index { |item| item == object }
end

def elem_indices(object)
  find_indices { |item| item == object }
end

def eql?(other)
  list = self
  loop do
    return true if other.equal?(list)
    return false unless other.is_a?(List)
    return other.empty? if list.empty?
    return false if other.empty?
    return false unless other.head.eql?(list.head)
    list = list.tail
    other = other.tail
  end
end

def filter(&block)
  return self unless block_given?
  Stream.new do
    next self if empty?
    next Sequence.new(head, tail.filter(&block)) if yield(head)
    tail.filter(&block)
  end
end

def find_index
  return nil unless block_given?
  i = 0
  list = self
  loop do
    return nil if list.empty?
    return i if yield(list.head)
    i += 1
    list = list.tail
  end
end

def find_indices(i = 0, &block)
  return EmptyList unless block_given?
  Stream.new do
    next EmptyList if empty?
    next Sequence.new(i, tail.find_indices(i + 1, &block)) if yield(head)
    tail.find_indices(i + 1, &block)
  end
end

def flat_map(&block)
  return self unless block_given?
  Stream.new do
    next self if empty?
    head_list = Hamster.list(*yield(head))
    next tail.flat_map(&block) if head_list.empty?
    Sequence.new(head_list.first, head_list.drop(1).append(tail.flat_map(&block)))
  end
end

def flatten
  Stream.new do
    next self if empty?
    next head.append(tail.flatten) if head.is_a?(List)
    Sequence.new(head, tail.flatten)
  end
end

def group_by(&block)
  return group_by { |item| item } unless block_given?
  reduce(EmptyHash) do |hash, item|
    key = yield(item)
    hash.put(key, (hash.get(key) || EmptyList).cons(item))
  end
end

def hash
  reduce(0) { |hash, item| (hash << 5) - hash + item.hash }
end

def index(object = Undefined, &block)
  return elem_index(object) unless object.equal?(Undefined)
  find_index(&block)
end

def indices(object = Undefined, &block)
  return elem_indices(object) unless object.equal?(Undefined)
  find_indices(&block)
end

def init
  return EmptyList if tail.empty?
  Stream.new { Sequence.new(head, tail.init) }
end

def inits
  Stream.new do
    next Sequence.new(self) if empty?
    Sequence.new(EmptyList, tail.inits.map { |list| list.cons(head) })
  end
end

def inspect
  to_a.inspect
end

def intersperse(sep)
  Stream.new do
    next self if tail.empty?
    Sequence.new(head, Sequence.new(sep, tail.intersperse(sep)))
  end
end

def join(sep = "")
  return "" if empty?
  sep = sep.to_s
  tail.reduce(head.to_s.dup) { |result, item| result << sep << item.to_s }
end

def last
  list = self
  list = list.tail until list.tail.empty?
  list.head
end

def map(&block)
  return self unless block_given?
  Stream.new do
    next self if empty?
    Sequence.new(yield(head), tail.map(&block))
  end
end

def merge(&comparator)
  return merge_by unless block_given?
  Stream.new do
    sorted = remove(&:empty?).sort do |a, b|
      yield(a.head, b.head)
    end
    next EmptyList if sorted.empty?
    Sequence.new(sorted.head.head, sorted.tail.cons(sorted.head.tail).merge(&comparator))
  end
end

def merge_by(&transformer)
  return merge_by { |item| item } unless block_given?
  Stream.new do
    sorted = remove(&:empty?).sort_by do |list|
      yield(list.head)
    end
    next EmptyList if sorted.empty?
    Sequence.new(sorted.head.head, sorted.tail.cons(sorted.head.tail).merge_by(&transformer))
  end
end

def method_missing(name, *args, &block)
  return accessor(Regexp.last_match[1]) if name.to_s.match(CADR)
  super
end

def pop
  Stream.new do
    next self if empty?
    new_size = size - 1
    next Sequence.new(head, tail.take(new_size - 1)) if new_size >= 1
    EmptyList
  end
end

def respond_to?(name, include_private = false)
  super || !!name.to_s.match(CADR)
end

def reverse
  Stream.new { reduce(EmptyList) { |list, item| list.cons(item) } }
end

def size
  reduce(0) { |memo, item| memo.next }
end

def slice(from, length = Undefined)
  return at(from) if length.equal?(Undefined)
  drop(from).take(length)
end

def sort(&comparator)
  Stream.new { Sorter.new(self).sort(&comparator) }
end

def sort_by(&transformer)
  return sort unless block_given?
  Stream.new { Sorter.new(self).sort_by(&transformer) }
end

def span(&block)
  return Tuple.new(self, EmptyList) unless block_given?
  Tuple.new(take_while(&block), drop_while(&block))
end

def split_at(number)
  Tuple.new(take(number), drop(number))
end

def tails
  Stream.new do
    next Sequence.new(self) if empty?
    Sequence.new(self, tail.tails)
  end
end

def take(number)
  Stream.new do
    next self if empty?
    next Sequence.new(head, tail.take(number - 1)) if number > 0
    EmptyList
  end
end

def take_while(&block)
  return self unless block_given?
  Stream.new do
    next self if empty?
    next Sequence.new(head, tail.take_while(&block)) if yield(head)
    EmptyList
  end
end

def to_list
  self
end

def to_set
  reduce(EmptySet) { |set, item| set.add(item) }
end

def union(other)
  append(other).uniq
end

def uniq(items = EmptySet)
  Stream.new do
    next self if empty?
    next tail.uniq(items) if items.include?(head)
    Sequence.new(head, tail.uniq(items.add(head)))
  end
end

def zip(other)
  Stream.new do
    next self if empty? && other.empty?
    Sequence.new(Sequence.new(head, Sequence.new(other.head)), tail.zip(other.tail))
  end
end