↓Skip to main content
  1. Readings/
  2. Books/
  3. Real World OCaml: Functional Programming for the Masses/

Chapter 10: Functors

··5291 words·25 mins
Table of Contents

Functors

We shift our focus back to OCaml’s modules.

Beyond the purpose of organising code into units with specified interfaces, we wish to see how they are useful in building generic code and structuring large-scale systems. Functors are essential for this.

Functors: functions from modules to modules, useful to structure:

  1. Dependency Injection

    • components of a system can become swappable
    • useful for mocking for testing and simulation

  2. Auto extension of modules

    • standardised way of extending modules with new functionality
    • we can write logic once and apply to different types

  3. Instantiating modules with state

    • functors allow automation of the construction of modules that have their own separate and independent mutable state

Functors are powerful for modularising code.

Costs of using Functors:

  1. syntactically heavyweight compared to other language features
  2. tricky issues to understand to use them properly – with sharing constraints and destructive substitution being some of them on that list

for small and simple programs, heavy use of functors is probably a mistake. But as your programs get more complicated and you need more effective modular architectures, functors become a highly valuable tool.

A trivial example #

open Base;;
module type X_int = sig val x : int end;;
(* module type X_int = sig val x : int end *)

(*-- this is the functor
  - X_int constraints the module returned by the functor
  - X_int constraints the argument to the functor
 *)
module Increment (M : X_int) : X_int = struct
  let x = M.x + 1
end;;
(* module Increment : functor (M : X_int) -> X_int *)

Functor syntax is a little extra:

  1. require explicit type annotations (module type annotations), ordinary functions don’t

    • only the type on the input is mandatory

  2. Nice to haves in practice:

    • should constraint the module returned by the function

      If we don’t, then the output type is inferred more specifically instead of being referenced by the named signature (X_int)

           (* note the output type: it's written explicitly instead of being referenced by the named signatture *)
     module Increment (M : X_int) = struct
       let x = M.x + 1
     end;;
     (* module Increment : functor (M : X_int) -> sig val x : int end *)

    • should also use an mli even if it’s not mandatory

  3. Signature matching is what determines interoperability between functors and other modules. This satisfiability of signatures works similarly to OOP languages (Liskov Substitution Principle – between ‘Parent/child types’).

    • we can apply Increment to any module whose signature satisfies interface X_int. This is similar to how contents of an ml file must satisfy the mli.

      • Substitution loss: in the example below Three_and_more satisfies X_int and therefore Increment can be used but because it has other fields (y), those fields are ignored by Increment. That’s why we see Four not having the field y.

    • module type can omit some information available in the module, either by dropping fields or leaving some fields abstract

          (* satisfies X_int => can be used by Increment *)
      module Three = struct let x = 3 end;;
      (* module Three : sig val x : int end *)
      module Four = Increment(Three);;
      (* module Four : sig val x : int end *)
      Four.x - Three.x;;
      (* - : int = 1 *)

      (* extending the interface (and it still matches) *)
      module Three_and_more = struct
        let x = 3
        let y = "three"
      end;;
      (* module Three_and_more : sig val x : int val y : string end *)
      module Four = Increment(Three_and_more);;
      (* module Four : sig val x : int end *)
      Four.x - Three_and_more.x;;
      (* - : int = 1 *)

A bigger example: computing with intervals #

We shall use functors to define a generic interval library that can be used with any type that supports a total ordering on the underlying set.

working with generic intervals usually has the usual operations:

  • emptiness check
  • containment check
  • intersection of intervals…
(* ===== 1. define the interface based on what kind of info we need from the endpoints of an interval
 , - it's essentially a comparator, with a type and a compare function.
   - the compare function usese the old school int-output comparison:
      * 0 if equal
      * 1 if first arg > second arg
      * -1 if first arg < second arg

 *)
module type Comparable = sig
  type t
  val compare : t -> t -> int
end;;
(* module type Comparable = sig type t val compare : t -> t -> int end *)


(* ===== 2: define the functor for making an interval *)
module Make_interval(Endpoint : Comparable) = struct

  (** Represent the interval as a variant type -- either Interval or Empty  *)
  type t = | Interval of Endpoint.t * Endpoint.t
           | Empty

  (** [create low high] creates a new interval from [low] to
      [high].  If [low > high], then the interval is empty *)
  let create low high =
    if Endpoint.compare low high > 0 then Empty
    else Interval (low,high)

  (** Returns true iff the interval is empty *)
  let is_empty = function
    | Empty -> true
    | Interval _ -> false

  (** [contains t x] returns true iff [x] is contained in the
      interval [t] *)
  let contains t x =
    match t with
    | Empty -> false
    | Interval (l,h) ->
      Endpoint.compare x l >= 0 && Endpoint.compare x h <= 0

  (** [intersect t1 t2] returns the intersection of the two input
      intervals *)
  let intersect t1 t2 =
    let min x y = if Endpoint.compare x y <= 0 then x else y in
    let max x y = if Endpoint.compare x y >= 0 then x else y in
    match t1,t2 with
    | Empty, _ | _, Empty -> Empty
    | Interval (l1,h1), Interval (l2,h2) ->
      create (max l1 l2) (min h1 h2)
end;;
(*
  module Make_interval :
  functor (Endpoint : Comparable) ->
    sig
      type t = Interval of Endpoint.t * Endpoint.t | Empty
      val create : Endpoint.t -> Endpoint.t -> t
      val is_empty : t -> bool
      val contains : t -> Endpoint.t -> bool
      val intersect : t -> t -> t
    end
 *)

(* ============= 3: applying the functor (anon module example) *)
module Int_interval =
  Make_interval(struct (*NOTE: this functor input is an anonymous Module*)
    type t = int
    let compare = Int.compare
end);;
(*
module Int_interval :
  sig
    type t = Interval of int * int | Empty
    val create : int -> int -> t
    val is_empty : t -> bool
    val contains : t -> int -> bool
    val intersect : t -> t -> t
  end
*)

(* ======== 4: Directly using aligned library modules: works because these modules satisfy an extended interface for Comparable already *)
module Int_interval = Make_interval(Int);;
(*
module Int_interval :
  sig
    type t = Make_interval(Base.Int).t = Interval of int * int | Empty
    val create : int -> int -> t
    val is_empty : t -> bool
    val contains : t -> int -> bool
    val intersect : t -> t -> t
  end
*)
module String_interval = Make_interval(String);;
(*
module String_interval :
  sig
    type t =
      Make_interval(Base.String).t =
        Interval of string * string
      | Empty
    val create : string -> string -> t
    val is_empty : t -> bool
    val contains : t -> string -> bool
    val intersect : t -> t -> t
  end
*)

(* ============== 5: the ease of modifying the extensions thanks to functors: *)
module Rev_int_interval =
  Make_interval(struct
    type t = int
    let compare x y = Int.compare y x (*revered comparison*)
end);;
(* NOTE:
   since this is nominally typed, Rev_int_interval.t is different from Int_interval.t even if the structure is exactly the same.
   This is good because we treat them as having semantically different meaningsa and hence they shouldn't be treated as the same.
 *)
(*
module Rev_int_interval :
  sig
    type t = Interval of int * int | Empty
    val create : int -> int -> t
    val is_empty : t -> bool
    val contains : t -> int -> bool
    val intersect : t -> t -> t
  end
  *)

Notes:

  1. the Functor’s body has implementations of useful functions/primitives to interact with Intervals

  2. in the examples where we directly applied the functor to aligned libaries (Int, String)… there’s some learnings:

    1. the use of standardised interfaces (e.g. comparable) is what makes the codebase consistent and predictable
    2. also helps us use functors more easily.

  3. the functor is NOT abstract and that’s a problem because some of the invariants (like low <= high) is being manually handled via a creator function which can be bypassed.

    The use of create is like an initiator factory that does some dynamic logical checks to see if the input params are right (low <= high).

    However, it’s possible to bypass it:

       Int_interval.is_empty (* going through create *)
   (Int_interval.create 4 3);;
   (* - : bool = true *)


   Int_interval.is_empty (* bypassing create by using the Interval constructor*)
   (Int_interval.Interval (4,3));;
   (* - : bool = false *)

Making the functor abstract #

We can make the functor abstract by restricting the output of Make_interval with an interface.

In the code below, we get an abstract functor, but the type endpoint is not exposed and so we can’t construct an interval yet.

However, we see the following happen:

  1. we have a reference to the endpoint type within the new interface

  2. the functor returns this interface which is more restrictive than the anon one before.

  3. in the interface, we see the use of an abstract type endpoint which intentionally creates an abstraction barrier: users of this module will not know what type endpoint is concretised to since that type info is NOT exposed via the interface.

    Typically this is a good thing because:

    1. prevents dependencies on implementation details

    2. creates ADTs safely

    3. allows different internal representations later without breaking callers (e.g. by concretising it to a particular type and losing its abstract typing.)

module type Interval_intf = sig
  type t
  type endpoint (*-- this is an abstract type from the POV of consumers of this module, it gives us a way of referring to the endpoint type*)
  val create : endpoint -> endpoint -> t
  val is_empty : t -> bool
  val contains : t -> endpoint -> bool
  val intersect : t -> t -> t
end;;
(*
module type Interval_intf =
  sig
    type t
    type endpoint
    val create : endpoint -> endpoint -> t
    val is_empty : t -> bool
    val contains : t -> endpoint -> bool
    val intersect : t -> t -> t
  end
*)

(* we can re-write our Make_interval functor with this interface *)
module Make_interval(Endpoint : Comparable) : Interval_intf = struct
  type endpoint = Endpoint.t (* we keep a handle to the endpoint type*)
  type t = | Interval of Endpoint.t * Endpoint.t
           | Empty

  (** [create low high] creates a new interval from [low] to
      [high].  If [low > high], then the interval is empty *)
  let create low high =
    if Endpoint.compare low high > 0 then Empty
    else Interval (low,high)

  (** Returns true iff the interval is empty *)
  let is_empty = function
    | Empty -> true
    | Interval _ -> false

  (** [contains t x] returns true iff [x] is contained in the
      interval [t] *)
  let contains t x =
    match t with
    | Empty -> false
    | Interval (l,h) ->
      Endpoint.compare x l >= 0 && Endpoint.compare x h <= 0

  (** [intersect t1 t2] returns the intersection of the two input
      intervals *)
  let intersect t1 t2 =
    let min x y = if Endpoint.compare x y <= 0 then x else y in
    let max x y = if Endpoint.compare x y >= 0 then x else y in
    match t1,t2 with
    | Empty, _ | _, Empty -> Empty
    | Interval (l1,h1), Interval (l2,h2) ->
      create (max l1 l2) (min h1 h2)
end;;
(* module Make_interval : functor (Endpoint : Comparable) -> Interval_intf *)

(* --- since we haven't exposed the type =endpoint=, we can't construct an interval anymore: *)
module Int_interval = Make_interval(Int);;
(*
module Int_interval :
  sig
    type t = Make_interval(Base.Int).t
    type endpoint = Make_interval(Base.Int).endpoint
    val create : endpoint -> endpoint -> t
    val is_empty : t -> bool
    val contains : t -> endpoint -> bool
    val intersect : t -> t -> t
  end
*)
Int_interval.create 3 4;;
(*
Line 1, characters 21-22:
Error: This expression has type int but an expression was expected of type
         Int_interval.endpoint
*)

By “not exposed” we mean that the Int_interval.endpoint is still abstract. If we were to expose it, then we can say that endpoint is equal to Int.t (or generally speaking, Endpoint.t where Endpoint is the argument to the functor). A type is not exposed when it appears abstract in a module’s interface — that is, its name is visible, but its concrete implementation (what it’s equal to) is hidden. This happens because the module’s signature does not include a manifest equality for the type.

In such cases, clients cannot create, deconstruct, or assume equality between that type and another; they can only manipulate it through the operations provided by the module.

sharing constraints #

Other than explicitly tying down the type in the interface, one way we can expose the abstract type is by sharing constraints – compiler gets told that a given type equals some other type.

One way is via a sharing constraint that tells the compiler to expose the fact that a given type is equal to some other type. Syntax: <Module_type> with type <type1> = <type1'> and type <type2> = <type2'>

This gives a new signature that’s been modified so that the type1 defined within the module is equal to the type1' whose definition is outside of it.

doing the sharing @ the interface #

We can make a specialised version of the Interval_int and get a specialised version for ints by having Int_interval_intf where we share the constraint for the endpoint type:


(* the original, abstract interface without the constraint on the type:  *)
module type Interval_intf = sig
  type t
  type endpoint (*-- this is an abstract type from the POV of consumers of this module, it gives us a way of referring to the endpoint type*)
  val create : endpoint -> endpoint -> t
  val is_empty : t -> bool
  val contains : t -> endpoint -> bool
  val intersect : t -> t -> t
end;;
(*
module type Interval_intf =
  sig
    type t
    type endpoint
    val create : endpoint -> endpoint -> t
    val is_empty : t -> bool
    val contains : t -> endpoint -> bool
    val intersect : t -> t -> t
  end
*)

(* using a sharing constraint to create a specialized version of Interval_intf: *)
module type Int_interval_intf =
Interval_intf with type endpoint = int;;
(*
module type Int_interval_intf =
  sig
    type t
    type endpoint = int
    val create : endpoint -> endpoint -> t
    val is_empty : t -> bool
    val contains : t -> endpoint -> bool
    val intersect : t -> t -> t
  end
*)

doing the sharing @ the functor #

We can also use the sharing constraints in the context of a functor.

Common use case: when we want to expose that the following are related:

  • some of the types of the module being generated by the functor

    So this is the type endpoint in the new module (functor output)

  • some of the types of the module being fed to the functor

    And this is the type Endpoint.t from the module Endpoint (which is the functor argument.)

module Make_interval(Endpoint : Comparable)
  : (Interval_intf with type endpoint = Endpoint.t)
= struct

  type endpoint = Endpoint.t
  type t = | Interval of Endpoint.t * Endpoint.t
           | Empty

  (** [create low high] creates a new interval from [low] to
      [high].  If [low > high], then the interval is empty *)
  let create low high =
    if Endpoint.compare low high > 0 then Empty
    else Interval (low,high)

  (** Returns true iff the interval is empty *)
  let is_empty = function
    | Empty -> true
    | Interval _ -> false

  (** [contains t x] returns true iff [x] is contained in the
      interval [t] *)
  let contains t x =
    match t with
    | Empty -> false
    | Interval (l,h) ->
      Endpoint.compare x l >= 0 && Endpoint.compare x h <= 0

  (** [intersect t1 t2] returns the intersection of the two input
      intervals *)
  let intersect t1 t2 =
    let min x y = if Endpoint.compare x y <= 0 then x else y in
    let max x y = if Endpoint.compare x y >= 0 then x else y in
    match t1,t2 with
    | Empty, _ | _, Empty -> Empty
    | Interval (l1,h1), Interval (l2,h2) ->
      create (max l1 l2) (min h1 h2)

end;;
(*
module Make_interval :
  functor (Endpoint : Comparable) ->
    sig
      type t
      type endpoint = Endpoint.t
      val create : endpoint -> endpoint -> t
      val is_empty : t -> bool
      val contains : t -> endpoint -> bool
      val intersect : t -> t -> t
    end
    *)

(* ====== now we can do things that require the =endpoint= type to be exposed e.g. constructing intervals: *)
module Int_interval = Make_interval(Int);;
(*
module Int_interval :
  sig
    type t = Make_interval(Base.Int).t
    type endpoint = int
    val create : endpoint -> endpoint -> t
    val is_empty : t -> bool
    val contains : t -> endpoint -> bool
    val intersect : t -> t -> t
  end
  *)
let i = Int_interval.create 3 4;;
(* val i : Int_interval.t = <abstr> *)
Int_interval.contains i 5;;
(* - : bool = false *)

an alternative: destructive substitution #

Constraint sharing works but it’s a little ugly.

We can do better using destructive substitution. A bit of misnomer, there’s nothing destructive about destructive substitution, it’s just a way of creating a new signature by transforming an existing one.

destructive substitution of the interface signature #

Here, we modify the signature of Interval_intf and replacing endpoint with Endpoint.t everywhere, which deletes the definition of endpoint from the signature.

Syntax looks similar to the sharing constraint but we use := instead of =.

(* ==== using destructive substitution *)
module type Int_interval_intf =
Interval_intf with type endpoint := int;;
(*
module type Int_interval_intf =
  sig
    type t
    val create : int -> int -> t
    val is_empty : t -> bool
    val contains : t -> int -> bool
    val intersect : t -> t -> t
  end
*)

(* using a sharing constraint to create a specialized version of Interval_intf: *)
module type Int_interval_intf =
Interval_intf with type endpoint = int;;
(*
module type Int_interval_intf =
  sig
    type t
    type endpoint = int
    val create : endpoint -> endpoint -> t
    val is_empty : t -> bool
    val contains : t -> endpoint -> bool
    val intersect : t -> t -> t
  end
*)

destructive substitution in the context of the functor #

Similar to constraint sharing, we can do destructive substitution in the context of the functor. A little different from the substitution at the interface level, we have kept the type t in this interface as abstract and have exposed the type of the endpoint. This allows us to create values of type Int_interval.t using the creation function but not using the constructors directly (which would have allowed the violation of the module).

module Make_interval(Endpoint : Comparable)
  : Interval_intf with type endpoint := Endpoint.t =
struct
  (* the type t is abstract, and the type of the endpoint is exposed; so we can create values of type Int_interval.t *)
  type t = | Interval of Endpoint.t * Endpoint.t
           | Empty

  (** [create low high] creates a new interval from [low] to
      [high].  If [low > high], then the interval is empty *)
  let create low high =
    if Endpoint.compare low high > 0 then Empty
    else Interval (low,high)

  (** Returns true iff the interval is empty *)
  let is_empty = function
    | Empty -> true
    | Interval _ -> false

  (** [contains t x] returns true iff [x] is contained in the
      interval [t] *)
  let contains t x =
    match t with
    | Empty -> false
    | Interval (l,h) ->
      Endpoint.compare x l >= 0 && Endpoint.compare x h <= 0

  (** [intersect t1 t2] returns the intersection of the two input
      intervals *)
  let intersect t1 t2 =
    let min x y = if Endpoint.compare x y <= 0 then x else y in
    let max x y = if Endpoint.compare x y >= 0 then x else y in
    match t1,t2 with
    | Empty, _ | _, Empty -> Empty
    | Interval (l1,h1), Interval (l2,h2) ->
      create (max l1 l2) (min h1 h2)

end;;
(*
module Make_interval :
  functor (Endpoint : Comparable) ->
    sig
      type t
      val create : Endpoint.t -> Endpoint.t -> t
      val is_empty : t -> bool
      val contains : t -> Endpoint.t -> bool
      val intersect : t -> t -> t
    end
*)


(* ======= applying them: *)
module Int_interval = Make_interval(Int);;
(*
module Int_interval :
  sig
    type t = Make_interval(Base.Int).t
    val create : int -> int -> t
    val is_empty : t -> bool
    val contains : t -> int -> bool
    val intersect : t -> t -> t
  end
  *)
Int_interval.is_empty
(Int_interval.create 3 4);;
(* - : bool = false *)

(* attempting to bypass the creation function and using the constructor directly will error out *)
Int_interval.is_empty (Int_interval.Interval (4,3));;
(*
Line 1, characters 24-45:
Error: Unbound constructor Int_interval.Interval
*)

There’s no need to define the endpoint type alias in the body of the module because the endpoint type is gone from the interface.

Using Multiple Interfaces #

We wish to make our interval module serialisable – i.e. read and write intervals as a stream of bytes.

Our intermediate format for this shall be sexps: a parenthesised expression whose atoms are strings, it’s what Base uses as its common serialisation format.

For this case, we can use derivation annotations for types that will generate the converter functions (serialise and de-serialise).

We can’t directly apply the [@@deriving sexp] to type t within the Make_interval functor signature until we ensure that Endpoint.t satisfies Sexpable.S which is a signature that looks like this:

sig
  type t
  val sexp_of_t : t -> Sexp.t
  val t_of_sexp : Sexp.t -> t
end

We have two choices:

  1. Now, we can modify Make_interval to use the Sexpable.S and the Interval_intf interfaces. For the Sexpable.S interface, we use destructive substitution on the type t.

       module type Interval_intf_with_sexp = sig
     include Interval_intf
     include Sexpable.S with type t := t
   end;;
   (*
   module type Interval_intf_with_sexp =
     sig
       type t
       type endpoint
       val create : endpoint -> endpoint -> t
       val is_empty : t -> bool
       val contains : t -> endpoint -> bool
       val intersect : t -> t -> t
       val t_of_sexp : Sexp.t -> t
       val sexp_of_t : t -> Sexp.t
     end
     *)

  2. we can define type t within the new module and apply destructive substitutions to all the included interfaces. This is cleaner when combining multiple interfaces because it correctly reflects that all of the signatures are being handled equivalently:

    • Interval_intf

    • Sexpable.S

       module type Interval_intf_with_sexp = sig
     type t
     include Interval_intf with type t := t
     include Sexpable.S with type t := t
   end;;
   (*
   module type Interval_intf_with_sexp =
     sig
       type t
       type endpoint
       val create : endpoint -> endpoint -> t
       val is_empty : t -> bool
       val contains : t -> endpoint -> bool
       val intersect : t -> t -> t
       val t_of_sexp : Sexp.t -> t
       val sexp_of_t : t -> Sexp.t
     end
     *)

   (* Now, we can update our functor: *)
   module Make_interval(Endpoint : sig
       type t
       include Comparable with type t := t
       include Sexpable.S with type t := t
     end)
     : (Interval_intf_with_sexp with type endpoint := Endpoint.t)
   = struct
     type t = | Interval of Endpoint.t * Endpoint.t
              | Empty
     [@@deriving sexp]

     (** [create low high] creates a new interval from [low] to
         [high].  If [low > high], then the interval is empty *)
     let create low high =
       if Endpoint.compare low high > 0 then Empty
       else Interval (low,high)

     (* NOTE: here, we wrapped the autogenerated [t_of_sexp] to enforce
        the invariants of the data structure -- modification *)
     let t_of_sexp sexp =
       match t_of_sexp sexp with
       | Empty -> Empty
       | Interval (x,y) -> create x y (*-- creator function is what enforces our invariants.*)

     (** Returns true iff the interval is empty *)
     let is_empty = function
       | Empty -> true
       | Interval _ -> false

     (** [contains t x] returns true iff [x] is contained in the
         interval [t] *)
     let contains t x =
       match t with
       | Empty -> false
       | Interval (l,h) ->
         Endpoint.compare x l >= 0 && Endpoint.compare x h <= 0

     (** [intersect t1 t2] returns the intersection of the two input
         intervals *)
     let intersect t1 t2 =
       let min x y = if Endpoint.compare x y <= 0 then x else y in
       let max x y = if Endpoint.compare x y >= 0 then x else y in
       match t1,t2 with
       | Empty, _ | _, Empty -> Empty
       | Interval (l1,h1), Interval (l2,h2) ->
         create (max l1 l2) (min h1 h2)
   end;;
   (*
   module Make_interval :
     functor
       (Endpoint : sig
                     type t
                     val compare : t -> t -> int
                     val t_of_sexp : Sexp.t -> t
                     val sexp_of_t : t -> Sexp.t
                   end)
       ->
       sig
         type t
         val create : Endpoint.t -> Endpoint.t -> t
         val is_empty : t -> bool
         val contains : t -> Endpoint.t -> bool
         val intersect : t -> t -> t
         val t_of_sexp : Sexp.t -> t
         val sexp_of_t : t -> Sexp.t
       end
   *)

   (* ==== USAGE:  *)
   module Int_interval = Make_interval(Int);;
   (*
   module Int_interval :
     sig
       type t = Make_interval(Base.Int).t
       val create : int -> int -> t
       val is_empty : t -> bool
       val contains : t -> int -> bool
       val intersect : t -> t -> t
       val t_of_sexp : Sexp.t -> t
       val sexp_of_t : t -> Sexp.t
     end
     *)
   Int_interval.sexp_of_t (Int_interval.create 3 4);;
   (* - : Sexp.t = (Interval 3 4) *)
   Int_interval.sexp_of_t (Int_interval.create 4 3);;
   (* - : Sexp.t = Empty *)

Use-case: Extending modules #

We can use functors to generate type-specific functionality for a given module in a standardised way.

here’s a somewhat skeletal interface for a functional version of a FIFO queue.

  • problem: it’s quite skeletal, we could have had many useful helper functions that don’t appear in the interface. For a reference to what some common functions on container types look like, we can see the List type and see things like List.for_all and other useful helper functions available to us.
type 'a t

val empty : 'a t

(** [enqueue q el] adds [el] to the back of [q] *)
val enqueue : 'a t -> 'a -> 'a t

(** [dequeue q] returns None if the [q] is empty, otherwise returns
    the first element of the queue and the remainder of the queue *)
val dequeue : 'a t -> ('a * 'a t) option

(** Folds over the queue, from front to back *)
val fold : 'a t -> init:'acc -> f:('acc -> 'a -> 'acc) -> 'acc

and here’s the implementation.

  • Trick: we maintain an input list and an output list. This allows us to efficiently enqueue on the input list and dequeue from the output list.

    The input list is reversed and becomes the new output list.

open Base

type 'a t = 'a list * 'a list (* the abstract type is concretised in the implementation to hold two lists: input and output list*)

let empty = ([],[])

let enqueue (in_list, out_list) x =
  (x :: in_list,out_list)

let dequeue (in_list, out_list) =
  match out_list with
  | hd :: tl -> Some (hd, (in_list, tl))
  | [] ->
    match List.rev in_list with (* use the reverse of the input list if the output list is empty:*)
    | [] -> None
    | hd :: tl -> Some (hd, ([], tl))

let fold (in_list, out_list) ~init ~f =
  let after_out = List.fold ~init ~f out_list in
  List.fold_right ~init:after_out ~f:(fun x acc -> f acc x) in_list

Improving by using a Foldable module #

We don’t want to keep repeating the implementations for the container types.

We acknowledge that many of the helper functions can be derived from the fold function that we already implemented.

Instead of writing all the helper functions, we can define a functor that can add functionality to any of the containers that have a fold function. Foldable module here automates the process of adding helper functions to a fold-supporting container.

  • it contains a module signature S which defines the signature that is required to support folding.
  • contains a functor Extend that allows one to extend any module matching Foldable.S
open Base

(* S is the signature that needs to be satisfied by the Functor argument. *)
module type S = sig
  type 'a t
  val fold : 'a t -> init:'acc -> f:('acc -> 'a -> 'acc) -> 'acc
end

(* Extension is the signature of the output module of the functor *)
module type Extension = sig
  type 'a t
  val iter    : 'a t -> f:('a -> unit) -> unit
  val length  : 'a t -> int
  val count   : 'a t -> f:('a -> bool) -> int
  val for_all : 'a t -> f:('a -> bool) -> bool
  val exists  : 'a t -> f:('a -> bool) -> bool
end

(* For extending a Foldable module *)
module Extend(Arg : S)
  : (Extension with type 'a t := 'a Arg.t) = (*destructive substitution with the type within the functor argument*)
struct
  open Arg

  (*-- here are all the functions derived from the fold function.*)
  let iter t ~f =
    fold t ~init:() ~f:(fun () a -> f a) (* just applies the function as a side-effect*)

  let length t =
    fold t ~init:0  ~f:(fun acc _ -> acc + 1) (* counting accumulation*)

  let count t ~f =
    fold t ~init:0  ~f:(fun count x -> count + if f x then 1 else 0)


  exception Short_circuit

  let for_all c ~f =
    try iter c ~f:(fun x -> if not (f x) then raise Short_circuit); true
    with Short_circuit -> false

  let exists c ~f =
    try iter c ~f:(fun x -> if f x then raise Short_circuit); false
    with Short_circuit -> true
end

Now, the Extend functor (which takes in something that satisfies the signature for Foldable) can be used on Fqueue and we would have extended the functionality for Fqueue.

To apply the functor, we shall put the definition of Fqueue in a submodule called T and then call the functor (Foldable.Extend) on T.

This is the interface for the extended version of Fqueue:

type 'a t
include (module type of Fqueue) with type 'a t := 'a t
include Foldable.Extension with type 'a t := 'a t

This is the application of the functor:

include Fqueue
include Foldable.Extend(Fqueue)

Functors that Base provides #

Similar pattern for extension is provided by Base in the form of the following functors:

  • Container.Make: similar to Foldable.Extend
  • Comparable.Make: comparison function, with support for containers like maps and sets.
  • Hashable.Make: add support for hashing-based datastructures including hash tables, hash sets and hash heaps.
  • Monad.Make: for monadic libraries. Here, functor is used to provide a collection of standard helper functions based on the bind and return operators.