[Haskell-cafe] What's the deal with Clean?
wren ng thornton
wren at freegeek.org
Tue Nov 3 21:35:43 EST 2009
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.
While this comes up with fusion, it's not a new problem. The same sort
of thing is gotten at by distinguishing worst-case vs average-case
complexity, or amortized worst-case vs non-amortized wost-case, etc.
More information about the Haskell-Cafe