From: Robert Klemme <shortcutter@...>
Date: 2011-02-02T17:47:19+09:00
Subject: Re: What is the difference between a Ruby array and a list in Haskell or Lisps?

On Wed, Feb 2, 2011 at 9:15 AM, David Masover <ninja@slaphack.com> wrote:
> 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.

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

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