RE: [Caml-list] User-defined equality on types?

RE: [Caml-list] User-defined equality on types?

[Don Syme]

> 
> On Wed, 18 Apr 2001, John R Harrison wrote:
> 
> > I'd like to suggest allowing the user to define a chosen 
> interpretation
> > of the equality symbol, and perhaps the polymorphic 
> orderings too, on
> > each new (maybe just abstract) data type. This seems natural in the 
> > context of abstract data types with non-canonical 
> representation, giving
> > a kind of quotient type. 
> [snip]
> > Any opinions?
> 
> I support this suggestion. The standard equality/ordering/hashing
> functions are often adequate for most of the data structures, 
> and it would
> be useful to use them and just place a hook on specific types 
> to provide
> specialized implementation. It could almost be done with
> the "custom" block tag; the problem is that such blocks are 
> not garbage
> collected.  What about "custom Caml blocks" ?

I support the suggestion too.  In general I'm not a big fan of types
carrying much implicit functionality, but I like the "balance" that Caml
has struck by making hashing, equality, ordering and marshalling
available for all types.  And given that you can define these functions
for custom blocks, it cetainly makes sense to be able to define them for
types defined in Caml as well...

Cheers,
Don
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

[Caml-list] User-defined equality on types?

[John R Harrison]

I'd like to suggest allowing the user to define a chosen interpretation
of the equality symbol, and perhaps the polymorphic orderings too, on
each new (maybe just abstract) data type. This seems natural in the 
context of abstract data types with non-canonical representation, giving
a kind of quotient type. Has this ever been considered? Are there good
reasons against it? Of course, I'd be happy for behaviour to be
undefined if the user nominates, say, a non-reflexive or non-substitutive
"equality" relation.

At present, I find that it's often quite inconvenient to use complicated
structures involving abstract types. In particular, I use the type of
arbitrary-precision numbers a lot, and frequently end up having to
define variants of standard polymorphic operations like set union for
several different types involving ":num". This would be avoided if I
could just automatically interpret "=" on the type ":num" as the special
comparison operator "=/".

Any opinions?
 
John.
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] User-defined equality on types?

[Francisco Valverde Albacete]

Hi, please read below the question:

John R Harrison wrote:

> I'd like to suggest allowing the user to define a chosen interpretation
> of the equality symbol, and perhaps the polymorphic orderings too, on
> each new (maybe just abstract) data type. This seems natural in the
> context of abstract data types with non-canonical representation, giving
> a kind of quotient type. Has this ever been considered?

Have you considered using functors defining your datatype structures? In that way
you can customise the use of equality throught the whole module with something like:

module ParameterisedADT
    (Eq: sig
               type t
               val (=) : t -> t -> bool
            end)
    =
    struct
        (* code of the ADT with whatever uses of your own "="! *)
    end

you just have to supply a structure for formal parameter Eq with the adequate
semantics. The semantics of this new operation will be entirely up to the
implementation in the parameter module (you can do really strange things here).

Hope it helps.

            Fran Valverde

PS: I apologise for the lack of French version. My French is way too rusty to write
anything sensible with it. FVA.


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] User-defined equality on types?

[John R Harrison]

Hi Francisco,

| Have you considered using functors defining your datatype
| structures? In that way you can customise the use of equality
| throught the whole module with something like:
| [...]

Thanks for the suggestion; I hadn't considered using functors. But I'm
not quite sure I understand your idea completely. I see how I can
localize the instances of the custom equality operation, but it seems
I still need to make explicit reference to a non-standard equality
*outside* the module, and it doesn't happen "transparently", still
less in composite data structures. This is the critical thing that I
want. For example, suppose I have a type of integers modulo 2 with a
non-canonical representation and a user-defined equality relation:

  module Mod2 =
    struct
      type z2 = Integer of int
      let (=) (Integer m) (Integer n) = (m - n) mod 2 = 0
      let mk n = Integer n
      let dest(Integer n) = n mod 2
    end;;

I want all equality on type "z2" to use this defined equality
relation, including on the appropriate fields of composite data
structures where some but (maybe not all) components are of type
"z2". But this doesn't happen by default:

  # let x = Mod2.mk 3 and y = Mod2.mk 5;;
  val x : Mod2.z2 = Mod2.Integer 3
  val y : Mod2.z2 = Mod2.Integer 5
  # x = y;;
  - : bool = false

If I explicitly refer to Mod2.(=), then all is well:

  # Mod2.(=) x y;;
  - : bool = true

But this doesn't happen automatically on composite data structures:

  # (x,1) = (y,1);;
  - : bool = false

and if I open the module, the regular equality is hidden:

  # open Mod2;;
  # x = y;;
  - : bool = true
  # (x,1) = (x,2);;
  This expression has type Mod2.z2 * int but is here used with type Mod2.z2

Can I use your idea to set things up to do what I want?

Btw, Alain Frisch's message reminded me that one would also like to be
able to customize the generic hashing function to ensure it's substitutive
w.r.t. the defined equality relation.

Of course, the "z2" example is articifial. But there are lots of real
situations where one might want types to be represented
non-canonically. For example, I think the standard library's sets,
represented by quasi-balanced trees, are non-canonical.

John.
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] User-defined equality on types?

[Alain Frisch]

On Wed, 18 Apr 2001, John R Harrison wrote:

> I'd like to suggest allowing the user to define a chosen interpretation
> of the equality symbol, and perhaps the polymorphic orderings too, on
> each new (maybe just abstract) data type. This seems natural in the 
> context of abstract data types with non-canonical representation, giving
> a kind of quotient type. 
[snip]
> Any opinions?

I support this suggestion. The standard equality/ordering/hashing
functions are often adequate for most of the data structures, and it would
be useful to use them and just place a hook on specific types to provide
specialized implementation. It could almost be done with
the "custom" block tag; the problem is that such blocks are not garbage
collected.  What about "custom Caml blocks" ?


-- 
  Alain Frisch

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] User-defined equality on types?

[Xavier Leroy]

> I'd like to suggest allowing the user to define a chosen interpretation
> of the equality symbol, and perhaps the polymorphic orderings too, on
> each new (maybe just abstract) data type. This seems natural in the 
> context of abstract data types with non-canonical representation, giving
> a kind of quotient type. Has this ever been considered? 

Yes.  This was one of the first motivations for Haskell type classes,
I believe.

> Are there good reasons against it?

It's not easy to implement.  One can do it the Haskell way, by passing
around compiler-generated functions as extra arguments, but the
language extensions needed to declare ad-hoc polymorphic operations
and define implementations for these operations at particular types 
are fairly complex.  I'd rather not add Haskell's type classes to
OCaml :-)

Another route is to attach the special equality operation to values of
the types of interest.  OCaml allows this for abstract types that are
implemented entirely in C, via the "custom block" mechanism, but not
currently for datatypes implemented in Caml, like the "num" type.

The example of "num" is particularly tricky, since it is not even an
abstract type, just a regular sum type with 3 constructors.  Hence,
even if custom blocks were extended to contain pointers back into the
Caml heap, it would still be hard to use them for representing values
of the "num" type.

One workaround would be to implement the "num" type entirely in C,
which is what the ML-GMP library does, I think.  Another would be to
keep "num" values normalized at all times, so that structural equality
coincides with numeric equality.  Both may entail performance
penalties in some cases, though.

> At present, I find that it's often quite inconvenient to use complicated
> structures involving abstract types. In particular, I use the type of
> arbitrary-precision numbers a lot, and frequently end up having to
> define variants of standard polymorphic operations like set union for
> several different types involving ":num".

Agreed.  In OCaml, sets are presented as a functor, so you can easily
pass a non-standard ordering function and you don't have to duplicate
the code implementing sets.  But you still have to define the ordering
functions, which can be a bit of a pain for complex data structures
containing nums.

Cheers,

- Xavier Leroy
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] User-defined equality on types?

[Brian Rogoff]

On Mon, 23 Apr 2001, Xavier Leroy wrote:
> > I'd like to suggest allowing the user to define a chosen interpretation
> > of the equality symbol, and perhaps the polymorphic orderings too, on
> > each new (maybe just abstract) data type. This seems natural in the 
> > context of abstract data types with non-canonical representation, giving
> > a kind of quotient type. Has this ever been considered? 
> 
> Yes.  This was one of the first motivations for Haskell type classes,
> I believe.

Would the proposed generic polymorphism extension solve this problem? It
seems that it would, and it would be a clean solution. John, in case you 
haven't seen it it is a typeclass like approach where instead of defining 
a type class you define generic functions which have a typecase and
dispatch to the right function (like CLOS). 

> > Are there good reasons against it?
> 
> It's not easy to implement.  One can do it the Haskell way, by passing
> around compiler-generated functions as extra arguments, but the
> language extensions needed to declare ad-hoc polymorphic operations
> and define implementations for these operations at particular types 
> are fairly complex.  I'd rather not add Haskell's type classes to
> OCaml :-)

That's too bad. I was hoping that one day the nice features of Haskell
would get stol^H^H^H^Hused in some future ML and I've always envied 
Haskeller's their type classes. 

-- Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] User-defined equality on types?

[Andreas Rossberg]

Brian Rogoff wrote:
> 
> On Mon, 23 Apr 2001, Xavier Leroy wrote:
> > > I'd like to suggest allowing the user to define a chosen interpretation
> > > of the equality symbol, and perhaps the polymorphic orderings too, on
> > > each new (maybe just abstract) data type. This seems natural in the
> > > context of abstract data types with non-canonical representation, giving
> > > a kind of quotient type. Has this ever been considered?
> >
> > Yes.  This was one of the first motivations for Haskell type classes,
> > I believe.
> 
> Would the proposed generic polymorphism extension solve this problem?

Probably not, because unlike type classes generic functions are closed
and do not allow adding cases for new types later on.

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

"Computer games don't affect kids.
 If Pac Man affected us as kids, we would all be running around in
 darkened rooms, munching pills, and listening to repetitive music."
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr