Left-bias and non-structural equality.

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
24 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Left-bias and non-structural equality.

Jean-Philippe Bernardy
On 1/2/06, Adrian Hey <[hidden email]> wrote:

> On Sunday 01 Jan 2006 3:28 pm, Jean-Philippe Bernardy wrote:
> > Yes, union suffers from the same problem; both in Set and Map as well.
> > The testing code can now detect problems of left-biasing in presence
> > of non-structural equality. (That's what I wanted to implement before
> > applying the fix).
>
> Actually I was wondering whether or not the term "left-biasing" was
> particularly useful. It could be misleading for some functions.
>
> For example..
> -- | /O(n*log n)/. Create a set from a list of elements.
> fromList :: Ord a => [a] -> Set a
> fromList xs = foldlStrict ins empty xs
>   where ins t x = insert x t
>
> My interpretation of left biasing would be that if the input list contains
> multiple occurences of "equal" values then the first occurence is the one
> which is inserted in the Set and the rest are discarded. But AFAICS the
> this is not the case with the current Data.Set implementation (or with the
> clone I just produced). Both are right biased (at least according to my
> intuitive understanding of the term).

There is a "definition" of left-bias here:
http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Set.html

-- Note that the implementation is /left-biased/ -- the elements of a
-- first argument are always perferred to the second, for example in
-- 'union' or 'insert'.  Of course, left-biasing can only be observed
-- when equality is an equivalence relation instead of structural
-- equality.

...which says nothing about biasing inside a list.

> BTW, I think I would prefer the default behaviour of insert
> to be to retain existing elements because this allows the
> optimisation of not updating the data structure representing
> the set at all (which should help keep heap burn rate down).
> But I guess this is in effect assuming equality implies
> structural equality so others may not like it. Sigh...

The biggest problem with this is that Map.insert changes the value
corresponding to the inserted key inside the map, and since it is
observable even with structural equality, you can be certain that
quite some people rely on that behaviour. Making Set do the opposite
is rather counter-intuitive.

In summary, left-biasing is important even in with well-behaved
equality, in the case of Maps.

> <whine>
> I really wish this whole issue of how to properly deal with "things
> that are equal but may still be different somehow" would just go
> away :-) It's hard to be precise about what choice you've made, and
> whatever choice you do make usually seems arbitrary. Even when
> it doesn't make any semantic difference, the choice you make may
> well have an observable effect on space and time behavior.
> </whine>

I really wish it too. BTW, the fact that Map and Sets had many
problems with non-structural equality and biasing is quite revealing
that this is not such a big problem in practice. (For the record I had
to fix union and intersection in Set, and union*, intersection*,
differenceWith* and insertWith* in Map)

Non structural equality seemed not to have many proponents the last
time I discussed it. (See
http://www.haskell.org//pipermail/libraries/2004-March/001833.html and
following messages)
Yet, since haskell doesn't rule it out, I guess we have to provide a
consitent behaviour, if only to minimize the user's suprise.

On the other hand, I wish to deprecate all functions that implicitly
promote non-structural Equality, in order not to lead the unsuspecting
user to a dangerous path.

Interestingly enough, this brings us back to the origin of this
thread, namely insertWithKey. Changing it to follow the left-bias
rule, it now doesn't depend on the keys present in the map; and hence
becomes deprecated, for the reason David mentioned.

Cheers,
JP.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Adrian Hey
On Monday 02 Jan 2006 7:29 pm, Jean-Philippe Bernardy wrote:
> Non structural equality seemed not to have many proponents the last
> time I discussed it. (See
> http://www.haskell.org//pipermail/libraries/2004-March/001833.html and
> following messages)
> Yet, since haskell doesn't rule it out, I guess we have to provide a
> consitent behaviour, if only to minimize the user's suprise.

Well I think on the whole I agree with the views expressed by Cale (and
Robert Will on the above mentioned thread). Insisting on structural
equality seems too restrictive. If we insist on this then presumably
Sets can't (sensibly) be instances of Eq or Ord, so we couldn't have
Sets of Sets. (Hmm.. Sets of Sets.. seems like tries would be the way
to go here. I guess we do probably do need ListSet and ListMap..)

Anyway, the problem is we have one hole and two "equal" things, only
one of which can fit in the hole. Is there any reason why we can't
simply adopt the position that which one is chosen is unspecified and
the choice is entirely at the implementors discretion?

If this results in ambiguous programs then this is because the
corresponding instance of Ord (and presumably Eq too) is just broken,
and this is what needs to be fixed (or removed). If users can't define
sane instances of Eq and Ord for their types then they'll just have to
use the lower level APIs (eg. Data.Tree.AVL) and pass whatever is the
appropriate combining comparison as an explicit argument.

Regards
--
Adrian Hey
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Adrian Hey
Hello,

On Monday 02 Jan 2006 11:43 pm, Adrian Hey wrote:
> Anyway, the problem is we have one hole and two "equal" things, only
> one of which can fit in the hole. Is there any reason why we can't
> simply adopt the position that which one is chosen is unspecified and
> the choice is entirely at the implementors discretion?

Well we've had 24 hours of silence on this issue, so I assume this
indicates that there is no reason we can't adopt the above position :-)
So I vote we drop the left/right biasing distinction. This way lies
madness (as they say:-)

Instead we demand that instances of Eq and Ord are semantically
sane, as should be stated in the Haskell language definition,
(but isn't AFAIK for some reason).

So for all instances of Ord, the semantics regarding which of two (or
more) "equal" values is used should always be "Who knows? Who cares?".

If there's some good reason why we should care then the corresponding
type should not be an instance of Ord. So what should be done in cases
like this? It's tempting to think we should add HOF versions like
this..

insertUsing :: (a -> a -> COrdering a) -> a -> Set a -> Set a

But as others have pointed out, this is probably the wrong thing
to do as Sets should provide some kind of semantic guarantees
(not sure what :-) which may be broken if we allow arbitrary
"combining comparisons" to be used.

I think the right thing to do is to expose a non-overloaded API
for the underlying data structure implementation, but don't
call it a "Set" or "Map" or whatever. Call it exactly what it
is "AVL tree" or "Adams tree" or "trie" (or whatever).

If we don't expose this API, this leaves users no alternative but
to define *broken* instances of Ord (and maybe Eq too) if they
want to make use of the data structure, and then leaves them
scrutinising source code trying to figure out if biasing
is the way they need it (and if not, what the heck they can
do about it?). This is Bad Thing I think.

Regards
--
Adrian Hey

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Christian Maeder
Adrian Hey wrote:
> So I vote we drop the left/right biasing distinction. This way lies
> madness (as they say:-)

I would not like to drop biasing distinction, as I don't think this
costs too much. With biasing, maps could be implemented via "biased
sets" (Set (MapEntry a b)):

data MapEntry a b = a := b

instance Eq/Ord a => Eq/Ord (MapEntry a b) where
     compare (a1 := _) (a2 := _) = compare a1 a2

> If there's some good reason why we should care then the corresponding
> type should not be an instance of Ord. So what should be done in cases
> like this? It's tempting to think we should add HOF versions like
> this..
>
> insertUsing :: (a -> a -> COrdering a) -> a -> Set a -> Set a

It may also be possible to pass an order to "empty" and use it further
on. The major problem is if varying orders are used ie. for "union".

By good, bad or earlier design Data.Set/Map relies on Ord instances and
I'm quite content with it.

Cheers Christian
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Jean-Philippe Bernardy
In reply to this post by Adrian Hey
Hi,

On 1/4/06, Adrian Hey <[hidden email]> wrote:

> Hello,
>
> On Monday 02 Jan 2006 11:43 pm, Adrian Hey wrote:
> > Anyway, the problem is we have one hole and two "equal" things, only
> > one of which can fit in the hole. Is there any reason why we can't
> > simply adopt the position that which one is chosen is unspecified and
> > the choice is entirely at the implementors discretion?
>
> Well we've had 24 hours of silence on this issue, so I assume this
> indicates that there is no reason we can't adopt the above position :-)
> So I vote we drop the left/right biasing distinction. This way lies
> madness (as they say:-)

Ok for sets; but biasing is still a sound notion for maps, as we
discussed previously.

> Instead we demand that instances of Eq and Ord are semantically
> sane, as should be stated in the Haskell language definition,
> (but isn't AFAIK for some reason).
>
> So for all instances of Ord, the semantics regarding which of two (or
> more) "equal" values is used should always be "Who knows? Who cares?".

Agreed. Still, I have fixed the Current Data.Map and Data.Set so they
match what the documentation says.

> If there's some good reason why we should care then the corresponding
> type should not be an instance of Ord. So what should be done in cases
> like this? It's tempting to think we should add HOF versions like
> this..
>
> insertUsing :: (a -> a -> COrdering a) -> a -> Set a -> Set a
>
> But as others have pointed out, this is probably the wrong thing
> to do as Sets should provide some kind of semantic guarantees
> (not sure what :-) which may be broken if we allow arbitrary
> "combining comparisons" to be used.
>
> I think the right thing to do is to expose a non-overloaded API
> for the underlying data structure implementation, but don't
> call it a "Set" or "Map" or whatever. Call it exactly what it
> is "AVL tree" or "Adams tree" or "trie" (or whatever).
>
> If we don't expose this API, this leaves users no alternative but
> to define *broken* instances of Ord (and maybe Eq too) if they
> want to make use of the data structure, and then leaves them
> scrutinising source code trying to figure out if biasing
> is the way they need it (and if not, what the heck they can
> do about it?). This is Bad Thing I think.

We can have high-level types/API for maps and sets that rely on a
sound Ord instance and in return guarantees validity of the structure;
and a low level api for AVL trees that allows everything.

Additionally, we should provide "toAVLTree / unsafeFromAVLTree" to
convert between low and high level types. This allows the best of both
worlds; safety by default, and high-performance/flexibility if the
user wishes.

Cheers,
JP.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Jean-Philippe Bernardy
In reply to this post by Christian Maeder
On 1/4/06, Christian Maeder <[hidden email]> wrote:

> Adrian Hey wrote:
> > So I vote we drop the left/right biasing distinction. This way lies
> > madness (as they say:-)
>
> I would not like to drop biasing distinction, as I don't think this
> costs too much. With biasing, maps could be implemented via "biased
> sets" (Set (MapEntry a b)):
>
> data MapEntry a b = a := b
>
> instance Eq/Ord a => Eq/Ord (MapEntry a b) where
>     compare (a1 := _) (a2 := _) = compare a1 a2

I would discourage such a use. This is exaclty why we provide Maps, after all.

> > If there's some good reason why we should care then the corresponding
> > type should not be an instance of Ord. So what should be done in cases
> > like this? It's tempting to think we should add HOF versions like
> > this..
> >
> > insertUsing :: (a -> a -> COrdering a) -> a -> Set a -> Set a
>
> It may also be possible to pass an order to "empty" and use it further
> on. The major problem is if varying orders are used ie. for "union".
>
> By good, bad or earlier design Data.Set/Map relies on Ord instances and
> I'm quite content with it.

A "good" solution would require dependent types or its type-classes
emulation, but I think this is overkill.

Cheers,
JP.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Christian Maeder
Jean-Philippe Bernardy wrote:
>> data MapEntry a b = a := b
>>
>> instance Eq/Ord a => Eq/Ord (MapEntry a b) where
>>     compare (a1 := _) (a2 := _) = compare a1 a2
>
> I would discourage such a use. This is exaclty why we provide Maps, after all.

Agreed, but suppose you have Symbols with their positions. Then you may
like that a set of symbols is printed with the positions last (or first)
inserted, although positions are ignored in camparisons.

C.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Adrian Hey
In reply to this post by Christian Maeder
On Wednesday 04 Jan 2006 3:25 pm, Christian Maeder wrote:
> I would not like to drop biasing distinction, as I don't think this
> costs too much. With biasing, maps could be implemented via "biased
> sets" (Set (MapEntry a b)):
>
> data MapEntry a b = a := b
>
> instance Eq/Ord a => Eq/Ord (MapEntry a b) where
>      compare (a1 := _) (a2 := _) = compare a1 a2

Yikes! You've just done exactly the Bad Thing I was talking
about :-). This is broken IMO. E.G.

val :: MapEntry a b -> b

We can now have (val x) and (val y) yielding different results
even though x and y may be "equal", according to the above Ord
instance.

But I guess you know all this already, so I'm somewhat surprised
by this suggestion. I think we should be clear about why we define
classes (and instances thereof) at all. Is it because they provide
some kind of semantic guarantee, or because they save lazy
programmers the effort of passing arbitrary functions about
as explicit arguments? I hope it's the former :-)

Regards
--
Adrian Hey

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Arie Peterson
In reply to this post by Christian Maeder
Christian Maeder wrote:
>
> Agreed, but suppose you have Symbols with their positions. Then you may
> like that a set of symbols is printed with the positions last (or first)
> inserted, although positions are ignored in camparisons.
>
> C.


It seems that there are two uses of Set e:

1) the Ord-comparison of e's is a total ordering / Eq e implements
semantic equality;

2) Eq e is some equivalence relation, such as in Christian's example above.

I agree with Jean-Philippe that 2) must not be advocated: users should
always use a Map instead (e.g. Map Symbol Position, with 'real equality'
on Symbol).


Now, it may save effort to *implement* Map by doing exactly 2), with e =
MapElement a b. The work needed to reimplement Map would have to be
compared to the work needed to ensure that Set supports use 2).

However, this is purely a consideration of implementation, and does not
effect the user experience of Set and Map - provided that she only uses
Set as per 1).



Greetings,

Arie

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Christian Maeder
Arie Peterson wrote:
> It seems that there are two uses of Set e:
>
> 1) the Ord-comparison of e's is a total ordering / Eq e implements
> semantic equality;
>
> 2) Eq e is some equivalence relation, such as in Christian's example above.

This is more often the case than one might like. Even for the type Set
itself Eq/Ord can be observed differently by the debugging function
showTree.

> I agree with Jean-Philippe that 2) must not be advocated:

ok

> users should
> always use a Map instead (e.g. Map Symbol Position, with 'real equality'
> on Symbol).

if I have:

data Symbol = Symbol String Position
instance Eq/Ord Symbol -- compare String only

I'd rather like "Map Symbol Position" than "Map String Position" if I
want to be more explicit about positions.

> Now, it may save effort to *implement* Map by doing exactly 2), with e =
> MapElement a b. The work needed to reimplement Map would have to be
> compared to the work needed to ensure that Set supports use 2).
>
> However, this is purely a consideration of implementation, and does not
> effect the user experience of Set and Map - provided that she only uses
> Set as per 1).

Controlled bias is simply an additional benefit of the Data.Set library
implementation that you must not and are not encouraged to use (but that
may be helpful if you know what you are doing),

C.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Arie Peterson
Christian Maeder wrote:
>
>> 2) Eq e is some equivalence relation, such as in Christian's example
>> above.
>
> This is more often the case than one might like. Even for the type Set
> itself Eq/Ord can be observed differently by the debugging function
> showTree.

Yes. Let me refine where I picture the border of Good Use of Eq. Eq should
implement *conceptual* (semantic) equality. Haskell objects are often not
in one-to-one correspondence with the conceptual object they represent:
there may be many trees that represent the same set. When you're defining
a set, you consider those trees equal and that should be reflected in your
Eq instance.

>
>> users should
>> always use a Map instead (e.g. Map Symbol Position, with 'real equality'
>> on Symbol).
>
> if I have:
>
> data Symbol = Symbol String Position
> instance Eq/Ord Symbol -- compare String only
>
> I'd rather like "Map Symbol Position" than "Map String Position" if I
> want to be more explicit about positions.

In this case I would go for something like

] data Symbol = Symbol String
] instance Eq/Ord Symbol

so you *can* say "Map Symbol Position". IMO this better reflects what a
symbol 'is'. One might want to add

] type Occurrence = (Symbol,Position)

or even

] type Occurrence = MapElement Symbol Position


> Controlled bias is simply an additional benefit of the Data.Set library
> implementation that you must not and are not encouraged to use (but that
> may be helpful if you know what you are doing),

Agreed.


Greetings,

Arie

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re[2]: Left-bias and non-structural equality.

Bulat Ziganshin
In reply to this post by Jean-Philippe Bernardy
Hello Jean-Philippe,

Wednesday, January 04, 2006, 6:36:14 PM, you wrote:

JPB> We can have high-level types/API for maps and sets that rely on a
JPB> sound Ord instance and in return guarantees validity of the structure;
JPB> and a low level api for AVL trees that allows everything.

imho, it the best way. for rather complex datastructures it is best
to implement in low-level module just the all operations this
datastructure provides and add high-level modules, which models some
abstract data types (Map, Set, Foldable and so on) over this
implementation. moreover, imvho it is better to leave low-level
implementation open (i.e. export all functions and internal
datastructure) so that anyone can add new low-level functions to this
datatype (say, serialization), or use this low-level api to implement
new high-level ADTs


--
Best regards,
 Bulat                            mailto:[hidden email]



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Adrian Hey
In reply to this post by Jean-Philippe Bernardy
On Wednesday 04 Jan 2006 3:36 pm, Jean-Philippe Bernardy wrote:
> On 1/4/06, Adrian Hey <[hidden email]> wrote:
> > Well we've had 24 hours of silence on this issue, so I assume this
> > indicates that there is no reason we can't adopt the above position :-)
> > So I vote we drop the left/right biasing distinction. This way lies
> > madness (as they say:-)
>
> Ok for sets; but biasing is still a sound notion for maps, as we
> discussed previously.

Well I wouldn't use the term biasing at all for association
values in Maps. The choice is clearly semantically significant and
I guess both options should provided by the new Map API.

> > So for all instances of Ord, the semantics regarding which of two (or
> > more) "equal" values is used should always be "Who knows? Who cares?".
>
> Agreed. Still, I have fixed the Current Data.Map and Data.Set so they
> match what the documentation says.

Yes, though I wonder how many people actually rely on this being correct?
Not many I suspect, since the implementations themselves were incorrect
in several cases :-)

I still think specifying this at all was a mistake and we should
deprecate all these functions. Unfortunately they use a lot of good
names, so maybe the entire API should be deprecated and put in
separate module (Data.OldSet or something).

> We can have high-level types/API for maps and sets that rely on a
> sound Ord instance and in return guarantees validity of the structure;
> and a low level api for AVL trees that allows everything.
>
> Additionally, we should provide "toAVLTree / unsafeFromAVLTree" to
> convert between low and high level types. This allows the best of both
> worlds; safety by default, and high-performance/flexibility if the
> user wishes.

Yes, in the short term where we're only providing one polymorphic
Set type. But I think the longer term goal is to provide some
kind of type constructor class that allowed multiple possible
implementations of polymorphic sets (and multiple specialised
monomorphic implementations too). So we shouldn't assume the
underlying data structure is always going to be AVL trees.

Regards
--
Adrian Hey

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Christian Maeder
Adrian Hey wrote:
 > On Wednesday 04 Jan 2006 3:36 pm, Jean-Philippe Bernardy wrote:
 >> Agreed. Still, I have fixed the Current Data.Map and Data.Set so they
 >> match what the documentation says.
 >
 > Yes, though I wonder how many people actually rely on this being correct?
 > Not many I suspect, since the implementations themselves were incorrect
 > in several cases :-)

Fortunately not many people relied on biasing, but a few noticed a
"wrong" bias. So fixing this is an improvement! I think, performance is
hardly affected.

 > I still think specifying this at all was a mistake and we should
 > deprecate all these functions. Unfortunately they use a lot of good
 > names, so maybe the entire API should be deprecated and put in
 > separate module (Data.OldSet or something).

I can't follow you here.
Cheers Christian

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Adrian Hey
On Wednesday 04 Jan 2006 10:21 pm, Christian Maeder wrote:

> Adrian Hey wrote:
>  > On Wednesday 04 Jan 2006 3:36 pm, Jean-Philippe Bernardy wrote:
>  >> Agreed. Still, I have fixed the Current Data.Map and Data.Set so they
>  >> match what the documentation says.
>  >
>  > Yes, though I wonder how many people actually rely on this being
>  > correct? Not many I suspect, since the implementations themselves were
>  > incorrect in several cases :-)
>
> Fortunately not many people relied on biasing, but a few noticed a
> "wrong" bias. So fixing this is an improvement! I think, performance is
> hardly affected.

If they noticed it that can only be because they defined broken instances
of Ord :-). Though in all fairness the current overloaded (only) API
leaves little alternative (if you want access to the tree implementation).
This is what we want to discourage IMO (but of course we must provide
some alternative for cases like this).

>  > I still think specifying this at all was a mistake and we should
>  > deprecate all these functions. Unfortunately they use a lot of good
>  > names, so maybe the entire API should be deprecated and put in
>  > separate module (Data.OldSet or something).
>
> I can't follow you here.

I mean the new Set API should not make any promises regarding biasing,
but I guess the old biased API still needs to be made available for
those that rely on current biasing (albeit at the cost of changing
imports). Or they could just make local copies of Data.Set or the
AVL based clone I recently posted.

Regards
--
Adrian Hey







_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Adrian Hey
In reply to this post by Christian Maeder
On Wednesday 04 Jan 2006 5:37 pm, Christian Maeder wrote:

> Arie Peterson wrote:
> > It seems that there are two uses of Set e:
> >
> > 1) the Ord-comparison of e's is a total ordering / Eq e implements
> > semantic equality;
> >
> > 2) Eq e is some equivalence relation, such as in Christian's example
> > above.
>
> This is more often the case than one might like. Even for the type Set
> itself Eq/Ord can be observed differently by the debugging function
> showTree.

Well here's my take on this. If we have a module that exports a type
(that is an instance of Eq/Ord) and associated functions then either..

The type is a concrete data type, in which case we pretty much have to
go for structural equality.

or..

The type is an abstract type, in which case we are free to use a
more relaxed but semantically useful definition of "equality". But
we can't do this AND have the API contain functions which allow
users to discriminate between "equal" values. This is just broken
(IMO).

Regards
--
Adrian Hey



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Christian Maeder
In reply to this post by Jean-Philippe Bernardy
Jean-Philippe Bernardy wrote:

> On 1/4/06, Christian Maeder <[hidden email]> wrote:
>> I would not like to drop biasing distinction, as I don't think this
>> costs too much. With biasing, maps could be implemented via "biased
>> sets" (Set (MapEntry a b)):
>>
>> data MapEntry a b = a := b
>>
>> instance Eq/Ord a => Eq/Ord (MapEntry a b) where
>>     compare (a1 := _) (a2 := _) = compare a1 a2
>
> I would discourage such a use. This is exaclty why we provide Maps, after all.

I still agree, but it might be nice to have for testing, comparison, and
property specification purposes.

Christian
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Jean-Philippe Bernardy
On 1/5/06, Christian Maeder <[hidden email]> wrote:

> Jean-Philippe Bernardy wrote:
> > On 1/4/06, Christian Maeder <[hidden email]> wrote:
> >> I would not like to drop biasing distinction, as I don't think this
> >> costs too much. With biasing, maps could be implemented via "biased
> >> sets" (Set (MapEntry a b)):
> >>
> >> data MapEntry a b = a := b
> >>
> >> instance Eq/Ord a => Eq/Ord (MapEntry a b) where
> >>     compare (a1 := _) (a2 := _) = compare a1 a2
> >
> > I would discourage such a use. This is exaclty why we provide Maps, after all.
>
> I still agree, but it might be nice to have for testing, comparison, and
> property specification purposes.
>
> Christian
>

Indeed, that's what I did to write the left-bias testing code. As it
is, we can choose to enable or disable ill-defined Eq it when testing
any given specific collection data-type.

Cheers,
JP.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Okasaki, C. DR   EECS
In reply to this post by Jean-Philippe Bernardy
I've been having this argument with people for close to 10 years now.

There are two similar but separate notions: equality and equivalence,
where equality means "equivalent in all contexts" and equivalence means
"equal in some contexts but not necessarily in others".  (I'll leave it
to others to give the base case of this recursive definition. :-)  The
problem is that Haskell has only a single Eq class, and it seems safe to
assume that that is not going to change anytime soon.  So which should
it be, equality or equivalence?  Many people want it to be equality, for
reasons of mathematical purity, while many others want it to be
equivalence, because it is so bloody useful.

As I see it, if you are going to restrict yourself to only one of the
two, equivalence is the better choice.  Why?  Because code designed to
work with equivalence will still work if you happen to give it an
equality relation, but code designed to work with equality can break if
you happen to give it an equivalence relation.

Another issue is that many *many* data structures can inherently only
provide equivalence.  The essential difference between equality and
equivalence has to do with being able to substitute "equals for equals".
For most data structures that have internal invariants, you can freely
substitute equals for equals *outside* the abstraction boundary, but not
*inside* the abstraction boundary.  For example, you can't replace the
left subtree of a balance binary search tree with another subtree with
the same elements but a different shape, and expect the whole tree to
still be balanced.  The only way around this problem is to have an extra
"wrapper" type and explicitly wrap/unwrap your data every time it
crosses the abstraction boundary.

The way I dealt with this in Edison was to provide two versions of many
operations, such as insert and insertWith, where insert is designed with
equality in mind and insertWith is designed with equivalence in mind.  I
have some sympathy for the argument that this pollutes the API, but in a
way that is easy to understand if you understand the
equality/equivalence issue.  You might think that assuming equality will
simplify the API, but your users would still need to understand the
equality/equivalence issue or they are going to accidentally give you
equivalence relations.

-- Chris
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Left-bias and non-structural equality.

Adrian Hey
In reply to this post by Jean-Philippe Bernardy
On Thursday 05 Jan 2006 9:55 am, Jean-Philippe Bernardy wrote:

> On 1/5/06, Christian Maeder <[hidden email]> wrote:
> > > I would discourage such a use. This is exaclty why we provide Maps,
> > > after all.
> >
> > I still agree, but it might be nice to have for testing, comparison, and
> > property specification purposes.
> >
> > Christian
>
> Indeed, that's what I did to write the left-bias testing code. As it
> is, we can choose to enable or disable ill-defined Eq it when testing
> any given specific collection data-type.

So do you propose to specify biasing or not?

Regards
--
Adrian Hey


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
12