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.