[Haskell-beginners] Question on Lists

[Alexander Dunlap]

On Sun, Apr 19, 2009 at 12:24 PM, Nathan Holden <nathanmholden at gmail.com> 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