Polymorphism in OCAML


I looked through multiple OCaml books, tried to search in the internet, gone through different example projects and tutorials and youtube videos…

What is the way to do polymorphism in OCaml?

I found many places on how one defines an interface (signature) for module, (which is always told is analogue to Interface is other programming languages).

Basically. I want something similar to code below to work (without using explicit pattern matching).

module type S = sig
  type t
  val store: int -> t 
  val get: t -> int 

module A : S  = struct
  type t = int
  let store x = x
  let get a = a

module B : S  = struct
  type t = int array
  let store x = [|x|]
  let get b = b.(0)

let factory_creatе x = if x > 0 then (*use A.store x and return something *) else (*use B.store x and return something*)

let polymorphic_var = factory_create 123

let polymorphic_get v = (* implementation without explicit pattern matching or conditions : use only S.get *)

let value = polymorphic_get polymorphic_var

let res = assert (value = 123)

Is it supported in OCaml? What is idiomatic way to achieve polymorphism?
Thanks in advance.


P.S. I also found it is possible to do something like this:

let polymorphic_get (type a) (module M : S with type t = a) (x : a) = M.get x

So I though something like this may work, but I faced compiler errors I could not overcome :confused:

let polymorphic_store (x : int) = if x > 0 then (A, a.store x) else (B, B.store x)
let polymorphic_get (type a) (module M : S with type t = a) (x : a) = M.get x
let (M, t) = polymorphic_store 123 
let result = polymorphic_get int M t

1 Like

Parametric polymorphism with higher-order functions and parametric data types is often the more idiomatic way to design polymorphism in OCaml. Consequently, most programs tend to favour the data-side of the expression problem (with an enumeration of a finite number of possible data constructors, rather than an enumeration of a finite number of possible behaviors).

To cover the behavior-side of the expression problem in order to have an open-ended number of implementations of a finite set of behavior, you can use, in order of complexity and expressiveness:

  • record of closures
  • record of closures inside a GADT (for people familiar with GADTs, otherwise same complexity as first-class module)
  • objects
  • first-class modules
  • functors

For instance, your example can be covered by a single closure:

let factory_creatе x =
  if x > 0 then
     let s = A.store x in fun () -> A.get s
    let s = B.store x in fun () -> B.get s

let var = factory_create 123
let get v = v ()
let value = get var
let res = assert (value = 123)

A slightly less clever implementation would use a record of functions

type 'a store = { set: 'a -> unit; get:unit -> 'a}
let ref_store x =
  let r = ref x in {
     set = (fun x -> r := x); 
    get= (fun () -> !r)
let array_store x =
  let r =  [|x|] in {
    set = (fun x -> r.(0) <- x);
    get = (fun () -> r.(0))
let get r = r.get ()

A more straightforward implementation would use objects (or classes) directly

class ['a] id (x:'a)  = object
   val store = x
   method get = store
let get o = o#get

And for comparison, the data side (finite number of constructors and open-ended number of behaviors) implementation could define

type 'a data_store =
 | Id of 'a
 | Array of 'a array
let get s = 
  match s with
  | Id x -> x
  | Array x -> x.(0)
let v x = if Random.bool then Id x else Array [| x |]
let _ = assert ( get (v 123) = 123 )

Someone mentioned the expression problem!

I have notes on that. Around 6 approaches IIRC. (3 “non-solutions” and 3 “solutions”.)
There was this long discussion thread… “The shape design problem”
SpiceGuid covers it in their book (unfortunately the book link doesn’t work for me anymore).


Thank you for your reply.

Basically, closure based solutions are in one way or another just ‘in place’ implementations of objects.

First class modules - seems be quite close, but it’s still required to code in exact module (not module type) and its - it’s still impossible to pass different first class modules around without pattern matching.

Functors - this one I can’t wrap my head around - those are basically preprocessors (or templates), which is quite a different thing…

most programs tend to favour the data-side of the expression problem (with an enumeration of a finite number of possible data constructors, rather than an enumeration of a finite number of possible behaviors)

This makes sense, but requires quite significant mindshift change + seems like it works great when the program is developed fully in-house, but not so for example for libraries, where number of behaviours is finite by library version anyways, so freedom for infinite data is what library user usually has.

Thank you for your helpful reply!

1 Like

Thank you, your lecture looks really helpful! I’ll need some time to go through all the examples there.

1 Like

Functors are functions from module to module. Stdlib.Set is a good and hopefully understandable example of what a functor can do. Essentially, library code defines the required interface:

# #show Stdlib.Set.OrderedType;;
module type OrderedType = sig
  type t
  val compare : t -> t -> int

and then uses it without knowing the underlying type (because it’s abstract in the interface):

module Make (O : OrderedType) = struct
  let cmp = O.compare

thus achieving your flavor of interface-based polymorphism. users of the set functor can supply any module that conforms to the above interface and get back a set + ops from the functor application:

# module S = Set.Make(struct
    type t = int array
    let compare = (* some cmp function here, defined based on a spec of your choice *)
module S : sig
  type elt = int array
# S.add (* example of an operation that was defined in set.ml generically *);;
- : S.elt -> S.t -> S.t = <fun>

functor instantiation is explicit as you’ve seen, so if you want to also be generic over a functor, you might have your own functor and instantiate the former inside it.


One way to think about functor and modules is that:

  • modules are fancy records that can also contain types, not just values. With first class modules you can even build them dynamically

    module M = struct
      type t = int;
      let equal = Int.equal
    (* is roughly equivalent to *)
    let M = { t = int; equal = Int.equal }

    Unlike records, you don’t need to declare the type of modules beforehand, unless you want to use them as first-class modules. In that case, just like for records, you need to define the type (module type in that case) to build it.

  • functors are just functions that return a new module:

    module F(G : X) = struct
      let foo = G.bar
    (* is roughtly equivalent to *)
    let F G = { foo = G.bar }