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.<br>
<br>Abhay<br><br><div class="gmail_quote">On Sun, Jun 1, 2008 at 1:07 PM, apfelmus <<a href="mailto:apfelmus@quantentunnel.de">apfelmus@quantentunnel.de</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Tillmann Rendel wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="Ih2E3d">
Abhay Parvate wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
I think I would like to make another note: when we talk about the complexity<br>
of a function, we are talking about the time taken to completely evaluate<br>
the result. Otherwise any expression in haskell will be O(1), since it just creates a thunk.<br>
</blockquote>
<br>
I don't like this notion of complexity, since it seems not very suited for the analysis of composite expression in Haskell.<br>
<br></div><div class="Ih2E3d">
Is this intuitive view generalizable to arbitrary datatypes (instead of lists) and formalized somewhere?<br>
</div></blockquote>
<br>
See also the thread section beginning with<br>
<br>
<a href="http://thread.gmane.org/gmane.comp.lang.haskell.cafe/34398/focus=34435" target="_blank">http://thread.gmane.org/gmane.comp.lang.haskell.cafe/34398/focus=34435</a><br>
<br>
<br>
<br>
Regards,<br><font color="#888888">
apfelmus</font><div><div></div><div class="Wj3C7c"><br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div><br>