I wonder whether the Ord instance is a good choice as constraint for
Data.Map, Data.Set and so on. I want to manage complex numbers and residue
classes in a set, or polynomials as keys of maps, but I hesitate to make
them instances of Ord, because "a
Henning Thielemann wrote:
I wonder whether the Ord instance is a good choice as constraint for Data.Map, Data.Set and so on.
In the case where there are Ord instances they are a good choice. Adding another type class for this purpose has the disadvantage that you have to write class instances for them, for all existing types that have Ord instances; while trivial this still adds up to quite a few lines of boilerplate code. This has to be weighted against the added boilerplate code for cases where a total order can be defined but is rather artificial. Right now I think that this is the exception rather than the rule. Changing the library interface should also not be done lightly. [snip examples: Complex numbers and Haskore notes]
I have a work-around in mind: I could introduce
class Eq a => Indexable a where compareIndex :: a -> a -> Ordering
[snip] Personally I'd do it without an Indexable class; just
newtype Index a = Index a
instance Ord x => Ord (Index (Complex x)) where (Index (Complex a b)) `compare` (Index (Complex c d)) = (a, b) `compare` (c, d)
should be good enough. 'Index' marks the purpose for the type. Note that for me, Ord alone really only implies a total order. If a type has both Num and Ord instances that is different; I understand your concerns about providing an Ord instance for Complex numbers directly.
Then I do not insert complex numbers immediately in a set, but wrap them in IndexableToOrd and insert the wrapped values in a set. Cumbersome, isn't it?
Of course you still need that index wrapping. If this gets out of hand it can be put into a simple wrapper around Data.Map though, without changing any existing libraries.
So my question is: Was the Ord constraint for Data.Map a good idea?
I still think it was. Bertram
On Tue, 17 Apr 2007, Bertram Felgenhauer wrote:
Henning Thielemann wrote:
I wonder whether the Ord instance is a good choice as constraint for Data.Map, Data.Set and so on.
In the case where there are Ord instances they are a good choice. Adding another type class for this purpose has the disadvantage that you have to write class instances for them, for all existing types that have Ord instances; while trivial this still adds up to quite a few lines of boilerplate code. This has to be weighted against the added boilerplate code for cases where a total order can be defined but is rather artificial. Right now I think that this is the exception rather than the rule. Changing the library interface should also not be done lightly.
I always think in terms of "How would it be done correctly if we would start from scratch?" :-)
Personally I'd do it without an Indexable class; just
newtype Index a = Index a
instance Ord x => Ord (Index (Complex x)) where (Index (Complex a b)) `compare` (Index (Complex c d)) = (a, b) `compare` (c, d)
should be good enough. 'Index' marks the purpose for the type.
That requires extended instance declarations, doesn't it?
Henning Thielemann wrote:
instance Ord x => Ord (Index (Complex x)) where (Index (Complex a b)) `compare` (Index (Complex c d)) = (a, b) `compare` (c, d)
should be good enough. 'Index' marks the purpose for the type.
That requires extended instance declarations, doesn't it?
Aha. Yes it does. I don't see any simpler workaround than the one you proposed then, while sticking to Haskell 98. Thanks, Bertram
Henning Thielemann wrote:
I wonder whether the Ord instance is a good choice as constraint for Data.Map, Data.Set and so on. I want to manage complex numbers and residue classes in a set, or polynomials as keys of maps, but I hesitate to make them instances of Ord,
So basically you want local instances, let m :: Data.Set.Set Foo m = Data.Set.fromList [ .... ] where instance Ord Foo where .... Inability to do so is the "fundamental problem" with type classes (+ instances): they inhabit (pollute) a global space. If you write a library using type classes (interfaces), (as they told you in elementary school), then you force the user contribute to this pollution :-) The above (local instance) could be modelled by handing the required Ord dictionary explicitely (or as an implicit parameter, which I would not recommend, though) You can hand over the Ord dictionary when constructing a Set in Java:
TreeSet(Comparator comparator) Constructs a new, empty tree set, sorted according to the specified comparator.
So the Haskell collections could need a similar constructor? The difference to your work-around (Wrapper class for the elements of the collection) is that the constructor is called only once, but your wrapper clutters each and every access. (unrelated rant:) look at the above example code. Using qualified names is generally the right thing (TM) to do, but I still think that resulting type names as Data.Set.Set look distinctively ugly, almost like a typo. I would really love some shortcut (allowing to write "Data.Set" ) if a module export just one type. Best regards, J. W.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Johannes Waldmann wrote:
Henning Thielemann wrote: The above (local instance) could be modelled by handing the required Ord dictionary explicitely (or as an implicit parameter, which I would not recommend, though)
You can hand over the Ord dictionary when constructing a Set in Java:
TreeSet(Comparator comparator) Constructs a new, empty tree set, sorted according to the specified comparator.
So the Haskell collections could need a similar constructor? The difference to your work-around (Wrapper class for the elements of the collection) is that the constructor is called only once, but your wrapper clutters each and every access.
And then what do you do with (set1 `union` set2) where they have different comparators? C++ collections have that think-o, I don't know about Java.... the problem being that the comparators are not statically required to be "the same", just the same *type*, so, what do you do with two different ones? I suppose dependently-typed languages can directly express the equivalence requirement without requiring it to be statically determinable from the type system what the comparison operator is going to be. Compilers based on classes being functions from types to methods (jhc...) can't use the alternate-dictionary thing. But you can always directly have the (key -> key -> Ordering) function be part of your data structure for the same effect, and then you can see all the problems involved (serialization, interactions and comparisons between maps, etc.). If you just don't want to wrap and unwrap your *keys* all the time, perhaps you could have the statically checkable version: class Comparer comp where type ComparedType comp --associated type, not yet implemented anywhere compare' :: ~comp -> (ComparedType comp) -> (ComparedType comp) -> Ordering --the '~' means that that parameter must be unused (this is not an implemented syntax) (the parameter is only there to select which instance is being used, since you can't pass a type directly as an argument without an associated "value", in Haskell; rather, (undefined :: TheCorrectType) is passed) data NewMap comp k v = ...the same as Data.Map -- most operations on NewMap require the context (Comparer comp) data OrdComparer k --a "phantom" (data-)type with no constructors instance (Ord k) => Comparer (OrdComparer k) where type ComparedType (OrdComparer k) = k compare' = Prelude.compare type Map k = NewMap (OrdComparer k) k -- most operations on Map require the context (Ord k), which is a simplification of the required context (Comparer (OrdComparer k)) Isaac -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGJniXHgcxvIWYTTURAhNYAJ4+SWf6DO/gC0nLngopykIySKguQACfafdk kiD505V+pr2n2+BsOZS47Uo= =HTQ2 -----END PGP SIGNATURE-----
Isaac Dupree wrote:
And then what do you do with (set1 `union` set2) where they have different comparators?
Nice question! Looking at the JDK source, in the TreeSet implementation of Collection.addAll (..), they actually compare the comparator objects ( with .equals() , so you can define that as you like )
But you can always directly have the (key -> key -> Ordering) function be part of your data structure for the same effect,
Yes, I meant that function when I said "the Ord dictionary". Sorry for confusion.
and then you can see all the problems involved (serialization, interactions and comparisons between maps, etc.).
Well, of course the Haskell system cannot serialize or compare (anonymous) functions. In Java land, as the compare function is attached to a Comparator object, the burden of serialization is on the programmer. (also of writing the equality test mentioned above). Looks rather sensible to me, under the circumstances. Best regards, J. W.
On Wed, 18 Apr 2007, Isaac Dupree wrote:
And then what do you do with (set1 `union` set2) where they have different comparators? C++ collections have that think-o, I don't know about Java.... the problem being that the comparators are not statically required to be "the same", just the same *type*, so, what do you do with two different ones?
I expect that local instances of equal types provide equal method dictionaries, don't they? However I don't think that local instances solve the problem here. Locally used (<) for complex numbers should be regarded the same error like (<) for complex numbers everywhere.
(unrelated rant:) look at the above example code. Using qualified names is generally the right thing (TM) to do, but I still think that resulting type names as Data.Set.Set look distinctively ugly, almost like a typo. I would really love some shortcut (allowing to write "Data.Set" ) if a module export just one type.
I find myself writing, again and again, for these modules: import Data.Map (Map) import qualified Data.Map as Map and wondering, again and again, whether there might be a good way to abbreviate this pattern... In this context, I would also welcome an option to just import (unqualified) all operators, without having to list them all. Wolfram
participants (5)
-
Bertram Felgenhauer -
Henning Thielemann -
Isaac Dupree -
Johannes Waldmann -
kahl＠cas.mcmaster.ca