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?)
On Sun, Apr 19, 2009 at 12:24 PM, Nathan 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?)
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
participants (2)
-
Alexander Dunlap -
Nathan Holden