an immutable list that you can add to the front and remove from the back, and it returns a new list.

phoenix_list.rb

#Evan,
# This gets the idea out of my head but it is still messy.  There are no tests, it probably has errors on the edge
# conditions, etc.
#
# I'll revise it after the ruby user group meeting tonight.

# needed internally to the PhoenixList
class Node
  attr_accessor :value, :previous

  def initialize(value, previous = nil)
    @value = value
    @previous = previous
  end

end


# this needs a lot of work.  It could implement enumerable if we cared.
# if both are nil, we are empty.
# if @head == @tail, we have 1 element.
# @head should be .previous to seme depth to @tail
class PhoenixList
  attr_reader :head, :tail

  def initialize(head = nil, tail = nil)
    @head = head
    @tail = tail || head
  end

  def add(element)
    node = Node.new(element, @head)
    PhoenixList.new(node, @tail)
  end

  def to_a
    array = Array.new
    cursor = @head
    return array if @head == nil

    array << cursor.value
    return array if cursor.previous == nil
    begin
      cursor = cursor.previous
      array << cursor.value
    end until cursor == @tail
    array.reverse
  end


  # returns list with element removed, element
   def remove
     # optimization.  If we're empty, return ourself.
     if @head == nil
       return self, nil
     end

     # optimization - if this remove will make us empty, return a new Phoenixlist
     # so we are garbage collection friendly.
     if @head == @tail
       return (PhoenixList.new, @head.value)
     end

     cursor = @head
     new_tail_candidate = nil

     begin
       new_tail_candidate = cursor
       cursor = cursor.previous
     end until cursor == @tail

     new_list = PhoenixList.new(@head, new_tail_candidate)

     value = cursor ? cursor.value : nil

     return new_list, value
   end


end




 p0 = PhoenixList.new
 p1 = p0.add(1)
 p2 = p1.add(2)
 p3 = p2.add(3)



p0.to_a
# []
p1.to_a
# [1]
p2.to_a
# [1,2]
p3.to_a
#[1, 2, 3]

px, value = p3.remove
# value is 1
# px.to is [2, 3]