Ronald Guida wrote:
Thank you, apfelmus. That was a wonderful explanation; the debit
method in [1] finally makes sense.
A diagram says more than a thousand words :)
My explanation is not entirely faithful to Okasaki, let me elaborate.
In his book, Okasaki calls the process of transferring
Abhay Parvate wrote:
I somehow thought it would be easy to talk about complexity of calculating
individual elements in an infinite list should be sufficient, but that seems
to be involved, and my over-generalization doesn't seem to work. Thanks for
the link; particularly it has reference to
Thank you, apfelmus. That was a wonderful explanation; the debit
method in [1] finally makes sense.
[1]: Chris Okasaki. Purely Function Data Structures.
http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
___
Haskell-Cafe mailing list
Tillmann Rendel wrote:
Abhay Parvate wrote:
I think I would like to make another note: when we talk about the complexity
of a function, we are talking about the time taken to completely evaluate
the result. Otherwise any expression in haskell will be O(1), since it
just creates a thunk.
I
I somehow thought it would be easy to talk about complexity of calculating
individual elements in an infinite list should be sufficient, but that seems
to be involved, and my over-generalization doesn't seem to work. Thanks for
the link; particularly it has reference to Wadler's papers exactly on
Abhay Parvate wrote:
I think I would like to make another note: when we talk about the complexity
of a function, we are talking about the time taken to completely evaluate
the result. Otherwise any expression in haskell will be O(1), since it just
creates a thunk.
I don't like this notion of
Tillmann Rendel [EMAIL PROTECTED] writes:
Hi! (Cool, another guy from DAIMI on haskell-cafe!)
Another (n - 1) reduction steps for the second ++ to go away.
last (o ++ l)
A) ~ last ('o' : ++ l))
L) ~ last ( ++ l)
A) ~ last (l)
L) ~ 'l'
And the third and fourth ++ go away
I think I would like to make another note: when we talk about the complexity
of a function, we are talking about the time taken to completely evaluate
the result. Otherwise any expression in haskell will be O(1), since it just
creates a thunk.
And then the user of the program is to be blamed for
