On Thu, Apr 30, 2015 at 4:41 PM, Keean Schupke <[email protected]> wrote:
> On 29 April 2015 at 22:12, Matt Oliveri <[email protected]> wrote:
>>
>> Well, not really. Mathematically speaking, sets don't have an order;
>> that's an implementation issue. But whether it's nonsense or just a
>> bad idea is besides the point..
>
> I think this is missing the point. Sets and Ord are just an example.
Well I did say it was besides the point.
> There is only one ordering for a given type of set,
This is only true if instances of Ord are coherent.
> and the fast-union would require all sets
> to have the same type.
No it wouldn't. It needs the two sets it was passed to have the same
element type and ordering, and it needs to have access to the
comparator for that ordering.
> In this way you can make coherence a required property and it forces you to
> distinguish types, which is exactly what is required to statically determine
> which ordering to use.
How to statically determine the ordering is a different issue. That's
not necessarily possible with coherent typeclass instances either.
> The point of the implicit parameter is something else. You might sensibly
> define:
>
> union : Ord a => Set a -> Set a -> Set a
>
> and
>
> union : (a -> a -> Bool) -> Set a -> Set a -> Set a
>
> The idea with the implicit is that a single definition:
>
> union : {Ord a} -> Set a -> Set a -> Set a
>
> gives both functionalities. With no "ord" argument it behaves like the type
> class version, and with the ord argument, it behaves like the explicit
> comparison version (except the function needs to be wrapped in an Ord
> record).
I understand the gist of how instance arguments work. But you have not
addressed my point from before: with the ((a -> a -> Bool) -> Set a ->
Set a -> Set a) signature, the implementer doesn't know whether the
input sets agree on the order (without checking). Without coherent
instances, you wouldn't know with the typeclass signature either.
Instance arguments take advantage of the fact that coherence has been
forfeited, but without coherence, all of those signatures leave fast
union's requirement undocumented, that the inputs be ordered by the
available comparator.
> The point with the 'use' directive is that multiple imported modules may
> define different instances of Ord. with the use directive the order of
> imports does not affect the functionality, I import the sets I want and I
> choose which Ord definition is available implicitly, it doesn't matter if
> other modules define different Ord instances.
But it does matter if other modules define a different Ord instances
for the same type, because then any sets you receive from those
different modules may be ordered differently, and cannot correctly be
fast unioned. But you have no way of statically determining whether
this is the case. So to be conservative, you can't use fast union on
sets from other modules. This is basically what I said before, except
before I said it more rightly; it's really "sets from outside the
lexical scope of the 'use' directive".
_______________________________________________
bitc-dev mailing list
[email protected]
http://www.coyotos.org/mailman/listinfo/bitc-dev
