[Haskell-cafe] Re: appending an element to a list

apfelmus apfelmus at quantentunnel.de
Sun Jun 1 03:37:39 EDT 2008

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



More information about the Haskell-Cafe mailing list