[Haskell-cafe] Array functions?

[Michael Vanier]

> Date: Tue, 03 May 2005 19:56:00 -0400
> From: Daniel Carrera <dcarrera at digitaldistribution.com>
> 
> Hi Ben,
> 
> > Take a look at this one:
> > 
> > http://www.haskell.org/onlinelibrary/standard-prelude.html
> 
> Thanks.
> 
> What's the "Prelude" ?

It's the repository of haskell code (functions, types, type classes) that
is available without having to import any modules.  Basically, built-in
types, type classes, and functions.  You can also think of it as a module
that comes pre-loaded.

> >>1) Is there a function to get the ith element from an array?
> > 
> > From your own implementations I gather you mean 'list', not 'array'.
> 
> What's the difference?

_Big_ difference.  An array is a collection of items that provides O(1)
(constant time) access to any component via indexing, and (in imperative
languages) also provides constant-time changing (mutation) of any such
component.  A list (more specifically, a singly-linked list) is a
collection of items that consists of the front element (the "head" of the
list) and the rest of the list, which is another list (note that the empty
list is also a list).  The effect of this is that to get at an arbitrary
element of a list takes time proportional to the length of the list (it's
O(n), where n is the length of the list).  So you don't want to use lists
the same way you would use arrays -- they aren't "drop in replacements" for
arrays.  Doing so would result in horrendously inefficient code.  You need
to learn a new style of programming to work efficiently with lists,
typically involving using recursion on the head/tail structure of the list.
This mailing list isn't the right place to go into this in detail, but the
books I mentioned before (How to Design Programs and Structure and
Interpretation of Computer Programs) discuss this at great length.  This is
a lot of what makes functional programming hard for many people to learn;
you aren't just learning a new syntax, you're learning a whole new way to
think.  That's also what makes it fun ;-)

Mike