[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.
More information about the Haskell-Cafe