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.
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.