Polymorphic comparison - Githubissues

In SML the programmer gets for free an equality function for all equality types:

op= : ''a * ''a -> bool

This is great - it relieves the programmer from having to define equality for all of user-defined types (and records involving such types).

I suggest the Successor-ML adds polymorphic comparison, i.e. total ordering for all equality types:

compare : ''a * ''a -> order

The lack of polymorphic comparison in SML often practically forces programmers to use slow datastructures. Faced with the mundane task of writing long but trivial comparison functions, one often resorts to using a datastructure where only equality is required. E.g. one might use a set based on a list instead of one based on a tree.

Example. The type Exp represents expressions:

datatype Exp = Unary of int | Binary of Exp * Exp | Ternary of Exp * Exp * Exp

Now we want to count how many times each expression occured. We can use a finite map from expressions to their count. If we have the polymorphic comparison at our disposal, we are good to go.

However without polymorphic comparison, we need to write a trivial, yet very long and error-prone function:

fun compare_exp (Unary i, Unary j) = Int.compare (i,j)
  | compare_exp (Unary _, _) = LESS
  | compare_exp (_,Unary _) = GREATER
  | compare_exp (Binary(e1,e2), Binary(e3,e4)) = (case compare_exp (e1,e3) of
                                               EQUAL => compare_exp (e2,e4)
                                            | ord => ord)
  | compare_exp (Binary _, _) = LESS
  | compare_exp (_, Binary _) = GREATER
  | compare_exp ... = ... (* No, we're not done yet. *)

The polymorphic comparison should be easy to define and implement - after all equality is already there, and it's very similar. One just needs to define a standard order for datatypes and records.

I suggest datatypes are sorted in definition order. This will give the programmer an easy way to control the sorting order. In our example Unary < Binary < Ternary. If programmer wants to sort them for instance alphabetically, all that needs to be done is swap the order in the datatype definition to:

datatype Exp = Binary of Exp * Exp | Ternary of Exp * Exp * Exp | Unary of int

For records (including tuples) my suggestion is to sort first by #1, then by #2, then by #a, then by #z (i.e. analogous to Int.compare for numeric labels and String.compare for alphanumeric labels).

for semantic reasons there cannot be such a thing, but the functionality you are after is provided cleanly by "modular type classes", which have been implemented experimentally by karl crary. we should have these.

bob

On Jun 4, 2016, at 13:22, Ud71p notifications@github.com wrote:

In SML the programmer gets for free an equality function for all equality types:

op= : ''a * ''a -> bool

This is great - it relieves the programmer from having to define equality for all of user-defined types (and records involving such types).

I suggest the Successor-ML adds polymorphic comparison, i.e. total ordering for all equality types:

compare : ''a * ''a -> order

The lack of polymorphic comparison in SML often practically forces programmers to use slow datastructures. Faced with the mundane task of writing long but trivial comparison functions, one often resorts to using a datastructure where only equality is required. E.g. one might use a set based on a list instead of one based on a tree.

Example. The type Exp represents expressions:

datatype Exp = Unary of int | Binary of Exp * Exp | Ternary of Exp * Exp * Exp

Now we want to count how many times each expression occured. We can use a finite map from expressions to their count. If we have the polymorphic comparison at our disposal, we are good to go.

However without polymorphic comparison, we need to write a trivial, yet very long and error-prone function:

fun compare_exp (Unary i, Unary j) = Int.compare (i,j) | compareexp (Unary , ) = LESS | compare_exp (,Unary ) = GREATER | compare_exp (Binary(e1,e2), Binary(e3,e4)) = (case compare_exp (e1,e3) of EQUAL => compare_exp (e2,e4) | ord => ord) | compareexp (Binary , _) = LESS | compareexp (, Binary ) = GREATER | compare_exp ... = ... (* No, we're not done yet. *)

The polymorphic comparison should be easy to define and implement - after all equality is already there, and it's very similar. One just needs to define a standard order for datatypes and records.

I suggest datatypes are sorted in definition order. This will give the programmer an easy way to control the sorting order. In our example Unary < Binary < Ternary. If programmer wants to sort them for instance alphabetically, all that needs to be done is swap the order in the datatype definition to:

datatype Exp = Binary of Exp * Exp | Ternary of Exp * Exp * Exp | Unary of int

For records (including tuples) my suggestion is to sort first by #1, then by #2, then by #a, then by #z (i.e. analogous to Int.compare for numeric labels and String.compare for alphanumeric labels).

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.

incidentally, the “free equality” is implemented using an ad hoc version of modular type classes. there is no free equality, in fact, of the polymorphic type you state, there is instead an equality for each of a class of specific types, and the right one is chosen when the types are known.

bob

On Jun 4, 2016, at 13:22, Ud71p notifications@github.com wrote:

In SML the programmer gets for free an equality function for all equality types:

op= : ''a * ''a -> bool

This is great - it relieves the programmer from having to define equality for all of user-defined types (and records involving such types).

I suggest the Successor-ML adds polymorphic comparison, i.e. total ordering for all equality types:

compare : ''a * ''a -> order

The lack of polymorphic comparison in SML often practically forces programmers to use slow datastructures. Faced with the mundane task of writing long but trivial comparison functions, one often resorts to using a datastructure where only equality is required. E.g. one might use a set based on a list instead of one based on a tree.

Example. The type Exp represents expressions:

datatype Exp = Unary of int | Binary of Exp * Exp | Ternary of Exp * Exp * Exp

Now we want to count how many times each expression occured. We can use a finite map from expressions to their count. If we have the polymorphic comparison at our disposal, we are good to go.

However without polymorphic comparison, we need to write a trivial, yet very long and error-prone function:

fun compare_exp (Unary i, Unary j) = Int.compare (i,j) | compareexp (Unary , ) = LESS | compare_exp (,Unary ) = GREATER | compare_exp (Binary(e1,e2), Binary(e3,e4)) = (case compare_exp (e1,e3) of EQUAL => compare_exp (e2,e4) | ord => ord) | compareexp (Binary , _) = LESS | compareexp (, Binary ) = GREATER | compare_exp ... = ... (* No, we're not done yet. *)

The polymorphic comparison should be easy to define and implement - after all equality is already there, and it's very similar. One just needs to define a standard order for datatypes and records.

I suggest datatypes are sorted in definition order. This will give the programmer an easy way to control the sorting order. In our example Unary < Binary < Ternary. If programmer wants to sort them for instance alphabetically, all that needs to be done is swap the order in the datatype definition to:

datatype Exp = Binary of Exp * Exp | Ternary of Exp * Exp * Exp | Unary of int

For records (including tuples) my suggestion is to sort first by #1 https://github.com/SMLFamily/Successor-ML/issues/1, then by #2 https://github.com/SMLFamily/Successor-ML/pull/2, then by #a, then by #z (i.e. analogous to Int.compare for numeric labels and String.compare for alphanumeric labels).

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/SMLFamily/Successor-ML/issues/22, or mute the thread https://github.com/notifications/unsubscribe/ABdsdSDezDAUFtm7X9_GDlfUrNW-xT0iks5qIbRWgaJpZM4IuLNR.

A workaround could be something like:

val rec expProj = fn
  | Unary i =>
      [1, i]
  | Binary e1 e2 =>
      2 :: expProj e1 @ expProj e2
  | Ternary e1 e2 e3 =>
      3 :: expProj e1 @ expProj e2 @ expProj e3

fun compareExp (exp1, exp2) =
  List.collate Int.compare (expProj exp1, expProj exp2)

Example lazy version:

(* general util code *)

datatype 'a proj =
  | LEAF of 'a
  | NODE of int * 'a proj list
  | THUNK of unit -> 'a proj

fun projCompare leafCompare = let
  val rec projCompRec = fn
    | (THUNK t, p) =>
        projCompRec (t (), p)
    | (p, THUNK t) =>
        projCompRec (p, t ())
    | (LEAF l1, LEAF l2) =>
        leafCompare (l1, l2)
    | (NODE (i1, ps1), NODE (i2, ps2)) =>
        (case Int.compare (i1, i2) of
          | EQUAL => List.collate projCompRec (ps1, ps2)
          | ord => ord)
    | _ =>
        raise Fail "should not happen"
  in projCompRec
end

(* specific to exp *)

val rec expProj = fn
  | Unary i =>
      NODE (1, [LEAF i])
  | Binary e1 e2 =>
      NODE (2,
        [THUNK (fn () => expProj e1),
          THUNK (fn () => expProj e2)])
  | Ternary e1 e2 e3 =>
      NODE (3,
        [THUNK (fn () => expProj e1),
          THUNK (fn () => expProj e2),
          THUNK (fn () => expProj e3)])

fun compareExp (exp1, exp2) =
  projCompare Int.compare (expProj exp1, expProj exp2)

SMLFamily / Successor-ML

Polymorphic comparison #22