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?
On Wed, Feb 2, 2011 at 9:15 AM, David M. [email protected]
wrote:
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
FWIW, Common Lisp at least has also arrays.
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.