Shorter way to create an Ordered type?

Learning
1

Hello!

I’ve written this piece of code:

module BddNode =
    struct
        type t =
            | BddLeaf of bool
            | BddNode of string * int * int
        let compare x y =
            match (x, y) with
            | BddLeaf bx, BddLeaf by -> compare bx by
            | BddLeaf _, BddNode _ -> -1
            | BddNode _, BddLeaf _ -> 1
            | BddNode (x1, x2, x3) , BddNode (y1, y2, y3) ->
                compare (x1, x2, x3) (y1, y2, y3)
    end

module BddGraph = Map.Make(BddNode)

It compiles, but is it a way to automatically “derive” the OrderedType? I’ve found this stackoverflow answer: https://stackoverflow.com/questions/17173101/ordered-variant-types-and-subtypes-in-ocaml but this a bit old and it seems OCaml noticeably envolved from this time.

At least, is it a way to write the last case of the match like:
| BddNode vy , BddNode vx -> compare vx vy
?
(with this exact syntax, the compiler complains that the BddNode constructor ask for 3 parameters)

2

You are probably looking for https://github.com/ocaml-ppx/ppx_deriving (especially the plugin ord). This allows you to simply write :

  type t =
            | BddLeaf of bool
            | BddNode of string * int * int [@@deriving ord]

and then you’ll get a compare function for free (the default for tuple is a lexicographic order, for enumeration it is what you would expect - for a type foo = A | B, you get A < B )

4 Likes
3

The way you have defined it, the constructor BddNode expects 3 arguments. They cannot be collected into a tuple vx in the way you tried above. You could define another constructor BddNode1 of (string * int *int) which is a one-argument constructor that takes a tuple (note the parentheses). With that you could do the match as you wanted. Unfortunately, OCaml prints values of BddNode and BddNode1 in the exact same way. Afair there are differences in the representation of values of these types in memory but i can never remember the details.

1 Like