Practical example of applicative vs generative functors?

Learning
1

I’ve heard one of the main differences between SML and OCaml is applicative vs generative functors. I’ve read this post which has helped me understand what these terms mean, but does not give any insight into where this difference might come up, or why one would prefer one over the other.

Is it possible to give a simple, practical example demonstrating a situation where one has to be concerned with applicative vs generative semantics, and perhaps explain why SML and OCaml chose to make different choices in this regard?
TIA!

2

Note that OCaml has both applicative and generative functors nowadays.

Applicative functors are useful when different applications of the same functor with the same entry should yield the same types.

A good example is the set functor, when you write

module Int_set = Set.Make(Int)

the resulting type Int_set.t is “the” type of sets of Int.t integers ordered with the Int.compare order.
Thus, if two libraries defines this module, there is no reason to consider that the sets of one library should be incompatible with the sets of the other library.

Contrarily, generative functor always create completely fresh types. Consider for instance an Make_id module:

module Make_id (): sig
  type t
  val create: unit -> t
end  = struct
  type t = int
  let unique_stamp = Atomic.make 0
  let create x = Atomic.fetch_and_add unique_stamp 1 
end

Then applying the functor yield a new identifier type:

module First_ids = Make_id ()
module Second_ids = Make_id ()

The two identifier types are then guaranteed to be distinct, which is important to ensure that we never generate equal identifiers twice. This is common phenomenon as soon as the functor generate some global mutable state in the generated module.

7 Likes
3

Thanks. So is it correct to say that applicative functors is more useful when your module is purely functional code?

4

Purely functional module is one of the important use case for applicative functor indeed.

More precisely, in order to really make sense applicative functors require that two applications of the functor are observationally identical.

This is automatically achieved if your functor is purely functional. However, one could imagine a functor that create a non-shared cache which is not visible from the outside world. In this case, it might be fine to make the functor applicative.

Another point is that the module system stretches a bit the notion of effects, and some generative functors are designed to have effect only at the type level.

For instance, one could define a module with an inner generative functor which only role is to create fresh types:

module Unit: sig
  type 'a t
  val (+): 'a t -> 'a t -> 'a t
  val ( * ): 'a t -> 'b t -> ('a * 'b) t
  val ( *. ): float -> 'a t -> 'a t
  module New(): sig
     type u
     val one: u t
 end
end = struct
  type 'a t = float
  let ( + ) = ( +. )
  let ( * ) = ( *. )
  let ( *. ) = ( *. )
  module New ()  = struct 
     type u
     let one = 1.
  end
end

The idea is that this module can be used to create float with an unit that cannot be mixed by accident:

module Meter = Unit.New ()
module Second = Unit.New ()
let m = Meter.one
let s = Second.one
let ok = Unit. ( 2. *. m + 3. *. m)
let fail = Unit.( s + m )

Error: This expression has type Meter.u t
      but an expression was expected of type Second.u t
      Type Meter.u is not compatible with type Second.u

In other words,the New functor application has morally a side-effect even if the body of the functor is purely functional.

9 Likes