Attempt to code a parameterized compare

Hello,

My first attempt to code a compare function is like this. I understand it can be simpler than this but I am learning.
It is comparing the weights of edges. ‘implicit’ is a syntax error. I have read some documents which deal with this in an advanced way. Any simpler explanation ?

type graph
type vertex
 type edge
 
 val createemptygrah : unit -> graph
 
 module type EDGECOMPARE = sig
 type t
 val eq : t -> t -> bool
 end
 implicit module EDGECOMPARE_weight : EDGECOMPARE with type t = edge = struct
            type t = edge
            let eq l r = if l.weight < r.weight
                              true
                             else false
end

Thanks,
Mohan

Part of the problem is this because my code was in a .mli file.

(modules_without_implementation <modules>) specifies a list of modules that have only a .mli
or .rei but no .ml or .re file. Such modules are usually referred as mli only modules. They are not officially
supported by the OCaml compiler, however they are commonly used. Such modules must only define types.
Since it is not reasonably possible for dune to check that this is the case, dune requires the user to explicitly list
such modules to avoid surprises. Note that the modules_without_implementation field is not merged
in modules, which represents the total set of modules in a library. If a directory has more than one stanza and
thus a modules field must be specified, <modules> still need to be added in modules.

Now this code is in a .ml file. But I am still trying to understand if this is a way to code parameterized types. I am used to Java where due to type erasure most of the the types are lost after compilation. Here it seems we specialize code for each parameterized type. Moreover I couldn’t get ‘implicit’ to compile in dune. Maybe it is not still accepted.

type edge = ( int * int * int ) list
module type EDGECOMPARE = sig
type t
val compare : 'a list -> 'a list ->bool
end

module EDGECOMPARE_weight : EDGECOMPARE with type t = edge = struct
type t = edge
let compare l r = ( List.nth l ( List.length l/ 2 )) == ( List.nth r (List.length r/2))
end

Modular imlicits are indeed not in the compiler trunk, tho there are these old compiler variants available from opam:

$ opam switch list-available | rg implicit
ocaml-variants      4.02.1+modular-implicits               OCaml 4.02, with support for modular implicits.
ocaml-variants      4.02.1+modular-implicits-ber           OCaml 4.02, with support for modular implicits and staging.

You may be interested in the Modular Implicits thread to see the state of development and read about related stuff.

This defines equality on two lists based on whether the elements in the middle of each list are physically equal. This is because

  1. List.nth : 'a list -> int -> 'a, and just returns the single element located at the nth position in the index.
  2. The == operator " tests the identity of its arguments, by testing the physical equality of memory representations" (source)

Unless you’re after a very peculiar sort of equality, I don’t think this is what you want :slight_smile:

Using the OCaml standard library, a minimal definition of polymorphic equality lists is just

let equal_lists = (=)

this is because the equality operator is already polymorphic. Try it in the top level!

utop # [1;2;3;4] = [1;2;3;4];;
- : bool = true
utop # ["a"; "b"; "c"] = ["x"; "y"; "z"];;
- : bool = false

In OCaml parlance, compare functions usually express inequalities rather than equality. E.g., Int.compare : int -> int -> int where the Int.compare m n is -1 if m < n, 0 if m = n, and 1 if m > n. The standard OCaml library also provides a polymorphic compare function, and that too will work on lists out of the box.

See the section in RWO on polymorphic compare for caveats and good reasons to avoid using it when performance is a concern.

If you want to define your own polymorphic comparison function, over lists is to take an argument providing a comparison of each element. Here’s one possible implementation:

utop # let rec mycompare compare xs ys = 
match xs, ys with
| [], [] -> 0  (* two empty lists are equal *)
| _, []  -> 1  (* xs is greater than ys if xs is longer *)
| [], _  -> -1 (* xs is less than ys if xs is sorter *)
| x::xs, y::ys -> 
  let c = compare x y in 
  if c <> 0 then 
    c                        (* The first inequality between elements is our result *)
  else 
    mycompare compare xs ys  (* or keep comparing the elements *)
;;
val mycompare : ('a -> 'b -> int) -> 'a list -> 'b list -> int = <fun>

You use it like

utop # mycompare Int.compare [1;2;3] [9;10;11];;
- : int = -1
utop # mycompare String.compare ["foo"] ["baz"];;
- : int = 1

If you use a standard standard library replacment such as base or containers you’ll get the properly parameterized functions for all generally useful data structures.

Thanks.

So the code I have shown is like ‘interface implementation’ ? I mean that there is a signature in the first module which is implemented by modules that specialize the first one.This pattern is valid though. Right ?

The comparison of the middle element of a list is what I intended. It is just a representation of two nodes and edge which has weight( middle element ). I understand that for primitives like ints phycical
equality suffices. I have the book you mention and will look at that section.

Mohan

Ah, it seems I misunderstood most of what you are asking for. I’m afraid it’s still not terribly clear to me.

Your compare function has type 'a list -> 'a list -> bool, so it is parametric over the type variable 'a (this is just inherited from the parametricity of ==). Your EDGECOMPARE_weight module is indeed an implementation of your EDGECOMPARE interface. But I’m afraid I don’t know exactly what additional information or understanding you’re seeking. I’m not familiar with representations of graphs that represent edges as lists of triples of ints, so maybe a clear articulation or link to the kind of graph representation your trying to implement would help me understand?

Are you meaning for compare to be a comparison of two edges, or two lists of edges, or something else?

I understood a few more concepts after reading your mail. Really helpful.
The graph algorithm is a toy example. But I was trying to understand
why my code in a .mli file would show this error.
I thought the interface can be in a separate file and the implementation can be in other.

You need to add the following field to this stanza:

(modules_without_implementation test)

This will become an error in the future.

Thanks.

I’m glad the exchange is helpful!

I’ve encountered this error when there is an .mli file but nor corresponding .ml file implementing the interface. According to the dune docs

(modules_without_implementation <modules>) specifies a list of modules that have only a .mli or .rei but no .ml or .re file. Such modules are usually referred as mli only modules. They are not officially supported by the OCaml compiler, however they are commonly used. Such modules must only define types. Since it is not reasonably possible for dune to check that this is the case, dune requires the user to explicitly list such modules to avoid surprises. must be a subset of the modules listed in the (modules …) field.

While experimenting, I recommend not messing with .mli files at all. You can still play with and implement interfaces using the module type declarations in your ml file.