search

spl / dlist

Difference lists in Haskell
https://hackage.haskell.org/package/dlist
BSD 3-Clause "New" or "Revised" License
65 stars 15 forks source link

Added a Eq, Ord, Show and Alternative instance #1

Closed basvandijk closed 11 years ago

JohnLato commented 11 years ago

Are you sure about the Eq and Ord instances? I suspect they're bad practice in general, since they would require converting from a DList to a List on each comparison, which seems really wasteful. If you wanted to use them as keys in a map, or in a set, for example, you'd be much better of just using the list as a key.

I'm sure they have some value for one-off sorts of things, but in those cases the comparison functions are small enough that writing them inline is easy. I don't think it's worth the large performance penalty one would get otherwise.

spl commented 11 years ago

@JohnLato Your concern is valid. Thanks for pointing it out.

I'm guessing that, even though the Show instance also involves toList, you don't think it presents the same problem as Eq and Ord due to the typical usage patterns of the three?

It would be useful to have a benchmark to show how much of a performance hit the conversion introduces vs. using lists with/without left-nested appends. Without left-nested appends, the conversion would probably be a small hit. With left-nested appends, I expect the conversion to be faster than using lists directly since dlists append in linear time. Perhaps I will put together a set of microbenchmarks at some point in the future.

My first thoughts are that the instances are useful enough and that a comment on each instance saying that it uses toList might assuage your concerns.

basvandijk commented 11 years ago

I agree with both of you. I don't expect users to use them in production but they are useful when playing with difference lists. A comment on them explaining that they go via toList would be ideal.

ivan-m commented 11 years ago

Since you've defined a Show instance, why not a Read instance just to finish off the set?

spl commented 11 years ago

@ivan-m I agree. I plan to do that unless somebody else beats me to it. :smile:

JohnLato commented 11 years ago

@spl WRT Show instance, correct, I have no concerns. It's very uncommon to repeatedly show a value, whereas Ord/Eq very frequently involve multiple comparisons with at least some common items.

As to the actual performance, it's very possible I'm micro-optimizing or pessimizing without a benchmark :smile: Until data is presented, a comment seems ideal.