On Wed, Apr 29, 2015 at 1:47 AM, Keean Schupke <ke...@fry-it.com> wrote:
>
> On 29 Apr 2015 05:12, "Matt Oliveri" <atma...@gmail.com> wrote:
>> My understanding from the video is that with this kind of solution,
>> you still wouldn't be able to union sets efficiently, because the sets
>> may come from people using different Ord instances for the element
>> type. Unless the union code and both sets all come from within the
>> lexical scope of the same "use" directive; but that restriction seems
>> onerous.
>
> If the two orderings define uniqueness differently, say people ordered by
> age in one set, and people ordered by name in another, then to union them is
> a nonsense.
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.
> In some regards all sets need to use the same ordering.
That's precisely the argument for instance coherence. In your system
with local "use" directives, only locally-created sets are guaranteed
to use the same ordering. Who knows with a set passed in from outside
the lexical scope?
> The definition of union should be (using braces for the implicit parameter):
>
> union :: {Ord a} -> Set a -> Set a -> Set a
The meaning of that type is ambiguous, depending on whether you expect
instances to be coherent or not. Will all three sets be ordered
according to the implicit argument, or just the result? Fast union
depends on all three using the same order. If (Set a)s are allowed to
be in a different order anywhere in the program, you need some other
way to enforce that the (Set a)s you pass to fast union will in fact
use the same order as the (Ord a) you pass.
You know, when I say it that way, coherent Ord instances actually does
not seem like the right way to do fast union. Fast union makes sense
because the representation of sets are ordered, and the algorithm uses
that fact. This is tight coupling. It's not like union is an operation
someone else would add to ordered sets afterwards. So in this case, I
think Set really should be "tagged" with an ordering, and the type of
union should explicitly demand that the arguments use the same
ordering. Instance coherence happens to work too, but the need for
coherence is artificial: only the two arguments of any given call to
union need to agree.
_______________________________________________
bitc-dev mailing list
bitc-dev@coyotos.org
http://www.coyotos.org/mailman/listinfo/bitc-dev
