Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Parametricity in OCaml

I am a complete beginner in OCaml, but I keep seeing code similar to the following in introductory examples

let sum = List.fold ~f:(+.) ~init:0.0

What bothers me in this snippet is the explicit use of List.fold. In most languages I know, the explicit type of the container would be abstracted by the use of an interface, a trait or a typeclass, so that one could reuse this code to sum an array or any other sequential container.

What is the OCaml way to make this more generic?

like image 414
Andrea Avatar asked Mar 17 '23 21:03

Andrea


1 Answers

A more generic solution is to use functors:

module type Foldable = sig 
  type 'a t
  val fold : 'a t -> init:'b -> f:('b -> 'a -> 'b) -> 'b
end

module MakeSum(Container : Foldable) = struct
  let sum xs = Container.fold ~f:(+.) ~init:0.0
end

As you may noticed this extra parametricity comes with significant syntactic overhead. Indeed, we can reuse interfaces from Core to reduce it:

module MakeSum(Container : Container.T) = struct
  let sum xs = Container.fold ~f:(+.) ~init:0.0
end

or

module MakeSum(Container : Container.S1) = struct
  let sum xs = Container.fold ~f:(+.) ~init:0.0
end

Also, as an example, you maybe mostly interested not in parametrizing over container types, but over the summation operation and zero value. This particular example is implemented using first class functors (another option) in OCaml Core library, and every container implements this function:

  (** Returns the sum of [f i] for i in the container *)
  val sum
    : (module Commutative_group.S with type t = 'sum)
    -> t -> f:(elt -> 'sum) -> 'sum

Update

Indeed, at your particular case we can generalize even without functors, since you do not need to know type in order to implement your code. So we can just define generic sum as:

let sum fold xs = fold ~f:(+.) ~init:0.0
like image 52
ivg Avatar answered Mar 24 '23 22:03

ivg