[Haskell-cafe] Re: appending an element to a list
Tillmann Rendel
rendel at daimi.au.dk
Sat May 31 09:01:31 EDT 2008
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 complexity, since it seems not very suited
for the analysis of composite expression in Haskell. For example,
repeat 42
has infinite complexity according to your definition (it doesn't even
terminate if completely evaluated), but
take 5 $ repeat 42
has only constant complexity even if fully evaluated. It is not clear
how to reuse the finding about the complexity of (repeat 42) to
determine the complexity of (take 5).
Instead, my view of complexity in lazy languages includes the
interesting behaviour of the rest of the program as variables. For
example, (repeat 42) needs O(n) steps to produce the first n elements of
its output. Now, (take 5 x) restricts x to the first 5 elements, so
(take 5 $ repeat 42) needs O(min(n, 5)) = O(1) steps to produce the
first n elements of its output.
Is this intuitive view generalizable to arbitrary datatypes (instead of
lists) and formalized somewhere?
Tillmann
More information about the Haskell-Cafe
mailing list