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