Re: What is the difference between a Ruby array and a list in Haskell or Lisps?

On Wednesday, February 02, 2011 12:05:14 am Kevin wrote:
> As the title asks what is the difference between a Ruby array and a list in
> Haskell or the various Lisp dialects?  I've started playing around with
> Haskell and other functional languages like Emacs-lisp and Clojure.  I've
> noticed that the list construct in these languages feels very much like
> Arrays in Ruby.  Can someone tell me what makes these data structures alike
> as well as what makes them different from each other?

Ruby arrays are probably closest to C++ vectors or Java ArrayLists -- almost 
certainly implemented as a flat array structure. This means fast random 
access, but slow inserts anywhere but the beginning, as you have to shift all 
subsequent elements down.

Lists in Lisp-like languages tend to be implemented as linked lists. This 
means slow random access, but fast inserts. In Lisp, it also means you can end 
up with weird structures where the same sublist is part of two separate lists, 
a phenomenon which can't really happen with Ruby arrays, for better or worse 
-- usually worse, because while there may be the occasional performance 
benefit, this kind of thing can also lead to some really strange bugs.

You can certainly implement linked lists in Ruby, and I'd hope most Lisps 
would have some sort of array you can use when you need it. Since you 
mentioned Clojure, I'll mention that JRuby seems to have all sorts of 
unexpected syntactic sugar for talking to Java collections, so you can use 
ArrayList or LinkedList almost as if they were Ruby arrays:


require 'java'
import java.util.ArrayList
import java.util.LinkedList

a = ArrayList.new
b = LinkedList.new
c = (1..10).to_a

c.each do |x|
  a << x
  b << x
end

# These all work pretty much interchangeably now
p a[4]
p b.inject(&:+)   # may require 1.9 mode
p c.map(&:to_s).inject(&:+)

# If there's anything that absolutely insists on a Ruby array, well:
p a.to_a == c
p b.to_a == c


I'm probably only scratching the surface, but I think that makes the point. 
There's no reason you can't implement a linked list in Ruby (or C) and build 
an interface for it as transparent as that, if it's important that your linked 
list pretend to be an array.