Performance horrors

[Duncan Coutts]

On Fri, 2008-08-29 at 02:56 -0400, Cale Gibbard wrote:

> On a side note related to the request for inclusion of complexities,
> since Haskell is a lazy language, we really ought to have complexities
> written in terms of the demanded portion of the result. Of course,
> Data.Set and Data.Map are (structure) strict, so it doesn't affect
> them so much, but it would certainly be nice for the functions in
> Data.List to know the answer to "if If the input is size n and I only
> demand k of the elements of the result, then what is the complexity?",
> especially for things like sort, where a lazy implementation can, for
> instance, make the head of the list available in just O(n) time.

Yeah, that's fairly important, though it's quite subtle. For example
we'd probably say if we demand k elements of the result of map then it
costs proportional to k (though we're not accounting for the cost of the
function application to each element), but technically that's true for
cons or tail too, even though they only do O(1) work and do not change
the 'potential'/'cost' of the remainder of the list.

Probably we can gloss over the details for a simple indication in the
docs, but just for fun here's a spanner:

foldr (\x xs -> x `seq` (x:xs)) []

it's only O(1) to eval whnf. It adds O(n) work to the whole structure,
but that property doesn't distinguish it from

foldr (\x xs -> (x:xs)) []

the difference of course is that it identifies costs within the
structure. So when a function demands the spine it also has to pay the
cost of the elements up front.

Duncan