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?

Haskell-Cafe mailing list

Reply via email to