Question on Lists

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Question on Lists

Nathan M. Holden
I have been reading Chris Okasaki's PhD thesis on Purely Functional Data
Structures (www.cs.cmu.edu/~rwh/theses/*okasaki*.pdf) and it discusses his
idea of lazy lists (He uses Standard ML in the paper), and it raised some
questions for me.

To cut to the chase, my question is this:

Say I have list x of length n, and I have a single piece of data y. Does
  x ++ [y]
take more cycles, or the same as if I'd said y:[x] (which would get it on
the wrong side?)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20090419/cd6460bc/attachment.htm
Reply | Threaded
Open this post in threaded view
|

Question on Lists

Alexander Dunlap
On Sun, Apr 19, 2009 at 12:24 PM, Nathan Holden <[hidden email]> wrote:

> I have been reading Chris Okasaki's PhD thesis on Purely Functional Data
> Structures (www.cs.cmu.edu/~rwh/theses/okasaki.pdf) and it discusses his
> idea of lazy lists (He uses Standard ML in the paper), and it raised some
> questions for me.
>
> To cut to the chase, my question is this:
>
> Say I have list x of length n, and I have a single piece of data y. Does
> ? x ++ [y]
> take more cycles, or the same as if I'd said y:[x] (which would get it on
> the wrong side?)
>

y:x is O(1), while x ++ [y] is O(n), where n is the number of elements
in x. This is because in order to do x ++ [y], you need to traverse
all of the elements in x to get to the end, while y:x just puts it
onto the front, which is readily available without a traversal.

y:[x] is a type error, because that is the same as saying [y,x], but y
and x are not the same type so they can't be in a list together.

Alex