xander <[EMAIL PROTECTED]> wrote:
> is there an opposite (:) available in haskell?
> like, i can toss an element at the back of a list without
> O(n) fuss recursing bla??
You can cons an element onto the front of a list without modifying it, but
adding an item at the end of the list will modify the list. That's why you
can't do it in O(1) time.
To illustrate, here's a simple list:
lst = [1,2,3]
Internally, most functional languages will implement this as a singly-linked
list, with the name "lst" pointing to the "1" element, as follows:
"lst" --> 1 --> 2 --> 3
Now, if you cons an item onto "lst", like this:
lst2 = 0:lst
the name "lst2" points to a newly-created "0" element, which in turn is
linked to the same "1" element that "lst" points to. Note that the original
list is NOT duplicated; there is still only one copy of the list [1,2,3],
and it can be referenced both as the list "lst" and also as the tail of the
list "lst2". This is what makes it possible to cons an element onto a list
in O(1) time.
But to add an element to the _end_ of a list, you have to duplicate the
entire list, or else you'll not only create a new list, but also modify any
other lists that happen to share elements with the list you're adding to.
For example (using -: as the "add element at tail in O(1) time" operator
you're looking for):
lst = [1,2,3] (internally: lst --> 1 --> 2 --> 3)
lst2 = lst -: 4 (internally: lst2 --> 1 --> 2 --> 3 --> 4)
This might seem okay at first glance, but remember that you haven't
duplicated the original list (because we want O(1) performance); we've just
added a new element to its tail. This means that "lst2" is referencing the
same 1 --> 2 --> 3 nodes that "lst" is using. The problem is that the "3"
node is now pointing to a "4" node, which means that in defining "lst2",
we've modified "lst", which is obviously not acceptable. This is why the
operator you want doesn't exist, and why instead you have to say
lst2 = lst ++ [4]
which actually copies the elements of "lst", giving O(n) performance.
I'm not sure if this is in a FAQ somewhere, but it ought to be. I think
every newcomer to functional programming (or LISP) wonders about this.
Craig
