[Haskell-cafe] What's the deal with Clean?

wren ng thornton wren at freegeek.org
Thu Nov 5 20:13:28 EST 2009

Roman Leshchinskiy wrote:
> wren ng thornton wrote:
>> Roman Leshchinskiy wrote:
>>> On 04/11/2009, at 13:23, Daniel Peebles wrote:
>>>> In the presence of fusion (as is the case in uvector), it's hard to
>>>> give meaningful time complexities for operations as they depend on
>>>> what operations they are paired with. We need to think of a better way
>>>> to express this behavior in the documentation though.
>>> I have to disagree here. Fusion never makes the complexity of 
>>> operations worse. If it does, it's a bug.
>> I think the point was more that the relevant complexity bound can 
>> change in the presence of fusion. For a poor example: the first map 
>> over a list is O(n) but all subsequent ones in a chain of maps are 
>> O(1) with fusion. I'm sure there are better examples than that, but 
>> you get the idea. Some people may care to know about that latter 
>> complexity rather than just the "independent" complexity.
> I think asymptotic complexity is the wrong tool for what you're trying 
> to do. [...] Executing the two maps, be it one after another or interlocked,
> is linear simply because O(n) + O(n) = O(n), not because of fusion.

As I said, it was a bad example. Off-hand I can't think of any examples 
where fusion actually does affect asymptotic complexity rather than just 
reducing the constant factor. But I think such examples (if they exist) 
are what Daniel was concerned with, rather than any bugs where fusion 
makes the complexity (or constant factors) worse.

Live well,

More information about the Haskell-Cafe mailing list