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

[wren ng thornton]

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,
~wren