What is the difference between a Ruby array and a list in Haskell orLisps?

[Kevin]

[Note: parts of this message were removed to make it a legal post.]

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?

 

[David Masover]

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.

 

[Robert Klemme]

Ruby arrays are probably closest to C++ vectors or Java ArrayLists -- alm= ost
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 ca= n end
up with weird structures where the same sublist is part of two separate l= ists,
a phenomenon which can't really happen with Ruby arrays, for better or wo= rse
-- usually worse, because while there may be the occasional performance
benefit, this kind of thing can also lead to some really strange bugs.

While it is certainly true that implementations of these data
structures have certain performance properties the more striking
differences are in the interface and the semantics IMHO. These are
probably also the first to care about.

Common
All these model a sequence of items, i.e. position in the data
structure matters. There are no restrictions on the number of
occurrences of the same item (as opposed to set data structures for
example). Traversal is actually quite similar: in Ruby you invoke
Array#each and pass a block (an anonymous function) - and in
traditional Lisp you invoke a list traversal function (e.g. mapcar)
and pass another function which is invoked per element.

Different
Generally in functional languages data structures are immutable. If
you append to a list you create a new instance etc. Also, Ruby is
object oriented which means that the functionality is part of the
class. In traditional Lisp list operations are functions which
operate on lists and return lists. Also, in traditional Lisp you
typically need a list traversal to insert / remove in the middle of
the list while a Ruby Array can have insertions and removals anywhere
with a single method call.

Kind regards

robert

--=20
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

 

[Xavier Noria]

FWIW, Common Lisp at least has also arrays.