Can the array be reinvented in Ruby?

Question

This is just a hypothetical question, if you wouldn't have the Array and the Hash class, would there be any way of implementing an Array class in pure Ruby? How?

Answer 1

You could use a linked list, which would be horrendously inefficient, but possible. You could also use a binary tree (see above comments).

I guess, my point is: you couldn't get a decent array without lower level language support. The basic structure that I assume is used in the Ruby array is a C array (though I could be wrong). With such a fundamental type, lower level support will be crucial for anywhere decent performance.

Answer 2

You can implement [] in any object. For example:

def [](index)
    proxy_object.send(index.to_sym)
end

Answer 3

I guess that's not possible without low level programming features, specially pointers...

Answer 4

Sure you can. Ruby is a Turing-complete language. You can implement everything that you can implement in any language in Ruby.

Answer 5

Yes we can!

class MyArray
  include Enumerable

  def initialize
    @size = 0
  end

  def <<(val)
    instance_variable_set("@a#{@size}".to_sym, val)
    @size += 1
  end

  def [](n)
    instance_variable_get("@a#{n}")
  end

  def length
    @size
  end

  def each
    0.upto(@size - 1) { |n| yield self[n] }
  end
end

a = MyArray.new
a << 1
a << 2
p a.to_a     #=> [1,2]

This works by creating instance variables @a0, @a1, etc. on the object to represent array indices 0, 1, etc. It has constant time length and index operations. The rest of the operations (remove, etc.) are a bit more effort to implement, but it's absolutely possible.

Note that the constant time property for the index operation depends on the underlying Ruby runtime using an appropriate data structure for instance variables.