Modular Explicits in OCaml › Polymorphism [abs-polymorphism]

The most prevalent kind of abstraction is polymorphism. For example, List.length will work for all lists regardless of what kind of elements the list contains. However, polymorphism requires you to keep the polymorphic part of the type at arm's length. This can lead to suboptimal performance and/or limited usefulness.

List.mem is a good example; in order to be polymorphic List.mem relies on Stdlib.(=), the polymorphic equality operator. In turn, this operator achieves its polymorphism by performing a structural comparison of the runtime representation of its arguments.

A common way to overcome this is to use higher-order functions (functions that take functions as arguments).

# let rec mem ?(eq=Stdlib.(=)) v = function
  | [] -> false
  | x :: xs -> eq v x || mem ~eq v xs
val mem : ?eq:('a -> 'a -> bool) -> 'a -> 'a list -> bool = <fun>
# let mem_int_list = mem ~eq:Int.equal
val mem_int_list : int -> int list -> bool = <fun>

This works well in plenty of cases (List.map, Hashtbl.iter, etc.), however, it doesn't scale well from a user's perspective if the body of the function requires lots of specific functions (e.g. compare, length, pp). At the same time, we want to avoid the precarious duck-typing of something like Python too.