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

Abhay

On Sun, Jun 1, 2008 at 1:07 PM, apfelmus <apfelmus@quantentunnel.de> wrote:
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 don't like this notion of complexity, since it seems not very suited for the analysis of composite expression in Haskell.

Is this intuitive view generalizable to arbitrary datatypes (instead of lists) and formalized somewhere?

See also the thread section beginning with

 http://thread.gmane.org/gmane.comp.lang.haskell.cafe/34398/focus=34435



Regards,
apfelmus


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe