How can I place functions in a set in Ocaml?

user_11683639 0
Viewed 72

I'd like make a Set module containing functions. But there seems to be no way to compare functions, which Set needs. This obvious-looking thing compiles:

module Action = struct
  type t = unit -> unit
  let compare : t -> t -> int = Stdlib.compare
end
module Actions = Set.Make(Action)

But if I attempt to use it:

Fatal error: exception Invalid_argument("compare: functional value")

I just want compare that the functions are the same object, I am not trying to do something silly like compare them for equal behaviour.

Am I supposed to use something from the Obj module here?

ocaml
3 Answers

The semantics of Stdlib.compare is to look arbitrarily deep inside the objects to see how their subparts compare. This doesn't really work for functions, as you point out. So OCaml doesn't allow compare to be applied to functions.

There isn't really a useful order that can be applied to functions, even if you're willing to use physical equality. Function values are immutable and can be duplicated or moved physically by the runtime system, at least in theory.

Since the ordering would necessarily be arbitrary, you can get the same effect by making your own arbitrary order: pair the functions with an int value that increases monotonically as you create new pairs.

user_8216790

Add an identity to your actions, e.g., you can compare actions by name,

module Action = struct 

  type t = {
    name : string;
    func : (unit -> unit);
  }

  let compare x y = String.compare x.name y.name
 end

You should also ensure that all actions have different names, for example by introducing a global hash table that records all created actions. Make sure that actions are only creatable via the Action module, by adding an appropriate signature.

user_26254420

OCaml Stdlib compare documentation states ...

val compare : 'a -> 'a -> int

compare x y returns 0 if x is equal to y, a negative integer if x is less than y, and a positive integer if x is greater than y. The ordering implemented by compare is compatible with the comparison predicates =, < and > defined above, with one difference on the treatment of the float value nan. Namely, the comparison predicates treat nan as different from any other float value, including itself; while compare treats nan as equal to itself and less than any other float value. This treatment of nan ensures that compare defines a total ordering relation.

compare applied to functional values may raise Invalid_argument. compare applied to cyclic structures may not terminate.

The compare function can be used as the comparison function required by the Set.Make and Map.Make functors, as well as the List.sort and Array.sort functions.

Now we have two notion(s) of equality in OCaml, namely...

  1. Structural Equality: Expressed using operator =, the type of which is
# (=);;
- : 'a -> 'a -> bool = <fun>
  1. Physical Equality: Expressed using operator ==, the type of which is
# (==);;
- : 'a -> 'a -> bool = <fun>

As we can see, the type of both is same, but the function application of both of them is different when it comes to function value as arguments.

Structural Equality doesn't hold over function values, but Physical Equality may. Trying to compare(as in =) with function values throws. And as stated in the documentation of Stdlib.compare, it uses structural equality.

Illustration: Structural Equality with Function Values

# let f x = x;;
val f : 'a -> 'a = <fun>
# let g x = x;;
val g : 'a -> 'a = <fun>
# f = g;;
Exception: Invalid_argument "compare: functional value".
# g = f;;
Exception: Invalid_argument "compare: functional value".

Illustration: Physical Equality with Function Values

# let f x = x;;
val f : 'a -> 'a = <fun>
# let g x = x;;
val g : 'a -> 'a = <fun>
# f == g;;
- : bool = false
# f == f;;
- : bool = true
# g == g;;
- : bool = true
# g == f;;
- : bool = false
# let h x y = x + y;;
val h : int -> int -> int = <fun>
# h == f;;
Error: This expression has type int -> int
       but an expression was expected of type int -> int -> int
       Type int is not compatible with type int -> int

So in short, I don't think we can use Stdlib.compare with Set.Make with function values.

So ...

  1. Either, we will have to keep the type t in Action module to something over which structural equality can be applied if we have to continue using Stdlib.compare.
  2. Or, implement compare of your own so that it can do something with those function values as arguments, along with satisfying the function contract of val compare : t -> t -> int as mandated by Set.OrderedType module type.

WYSIWYG => WHAT YOU SHOW IS WHAT YOU GET

user_116979360
Related