Make OCaml function polymorphic for int lists and float lists

Question

Is there a way to create a polymorphic add function in OCaml that works equally well for ints and floats? So for example if I have a function like:

partialsums [1; 2; 3; 4; 5] I should get [1; 3; 6; 10; 15] but this function won't work on [1.; 2.; 3.; 4.; 5.] because in OCaml ints and floats absolutely cannot be mixed. But what if I want my function to work equally well for int lists and float lists? Is there a general type of which int and float are sub-types? If so, what is it? I'm a little lost on this one. Thanks for the help?

Freeholder

Now my knowledge of OCaml is admittedly very limited, but even if you'd use parameterized types, you'd still need different operators (+ and +.) to build the partial sums since there is no polymorphic addition operator, right? – Bickart

Answer 1

Edit: While this answer holds theoretical value, you want to read neo's answer nowadays.

With parametric polymorphism, no. With ad-hoc polymorphism, yes.

For some type t, define a module,

module type Semigroup = sig
  type t
  val add : t -> t -> t
end

and some utility functions like partialsums that rely on this inside a functor,

module Utils (S : Semigroup) = struct
  let partialsums xs =
      match xs with
      | [] -> []
      | (x::xs) ->
          List.rev (snd (List.fold_left
            (fun (acc, ys) x -> let y = S.add acc x in (y, y::ys)) (x, [x]) xs))
end

you can get the partialsums specialized to particular types t,

module IntUtils = Utils(struct type t = int
                               let add = (+) end)
module FloatUtils = Utils(struct type t = float
                                 let add = (+.) end)

let int_test = IntUtils.partialsums [1; 2; 3; 4] ;;
let float_test = FloatUtils.partialsums [1.0; 2.0; 3.0; 4.0]

which is kind of cool, but also a little tedious; you still have to prefix your functions with something type-specific, but at least you only have to write the functions once. This is just the module system being awesome.

With modular implicits, yes, yes, yes!

With Modular Implicits (2014) by White, Bour and Yallop, you can write,

implicit module Semigroup_int =
  type t = int
  let add = (+)
end

implicit module Semigroup_float =
  type t = float
  let add = (+.)
end

implicit module Semigroup_string =
  type t = string
  let add = (^)
end

let add {S : Semigroup} x y = S.add x y

which will allow the definition of a generic and overloaded partialsums,

let partialsums xs =
    match xs with
    | [] -> []
    | (x::xs) ->
        List.rev (snd (List.fold_left
          (fun (acc, ys) x -> let y = add acc x in (y, y::ys)) (x, [x]) xs))

so now it does work equally well for ints and floats!

let int_test = partialsums [1; 2; 3; 4] ;;
let float_test = partialsums [1.0; 2.0; 3.0; 4.0]
let string_test = partialsums ["a"; "b"; "c"; "d"]

There have apparently been several attempts at unifying the ML module system and Haskell's notion of type classes. See e.g. Modular Type Classes (2007) by Dreyer, Harper and Chakravarty for a good background story.

Comprehensible

Great answer! A typo in implicit module Semigroup_string, I guess you meant type t = string. Also, snd is present in Pervasives (maybe it's in the answer for educational purposes, though). – Rameau

@AntonTrunov: Thanks. I didn't know Pervasives.snd existed. – Comprehensible

modular implicits aren't in OCaml just yet, though, are they? (as of 4.03) – Kristinakristine

Answer 2

The only common type for int list and float list is 'a list, i.e., a list of any type at all. Since the element type can be anything, there are no specific operations you can apply to the elements. So there's no straightforward way to write the function you want.

If you're willing to bundle up your list with a + function that operates on its elements, you can solve the problem that way.

let partialsums plus list =
    List.rev
        (List.fold_left
            (fun l n ->
                 if l = [] then [n] else (plus (List.hd l) n) :: l) 
            [] list)

# partialsums (+) [1;3;5;7];;
- : int list = [1; 4; 9; 16]
# partialsums (+.) [1.;3.;5.;7.];;
- : float list = [1.; 4.; 9.; 16.]

In this case, the list elements don't have to be numbers:

# partialsums (^) ["a"; "b"; "c"; "d"];;
- : string list = ["a"; "ab"; "abc"; "abcd"]

Another common solution is to use a variant type:

let numlist = Flist of float list | Ilist of int list

liet partialsums (list: numlist) =
    match list with
    | Flist l -> ...
    | Ilist l -> ...

Manicure

Answer 3

You can also try first-class modules as Base does (https://github.com/janestreet/base/blob/57240d0d8403031f37e105351d7d928a6aea1524/src/container.ml#L17), e.g.:

let sum (type a) ~fold (module M : Commutative_group.S with type t = a) t ~f =
  fold t ~init:M.zero ~f:(fun n a -> M.(+) n (f a))
;;

That gives you a pretty light-weight syntax:

List.sum (module Int) [1; 2; 3; 4; 5] ~f:Fn.id

Clarinda

This is by far the best answer today, since it relies on existing libraries and syntax that is available. :) In case it isn't clear to newcomers, Base is the name of Jane Street's alternative standard library. It requires one to use a package manager and does carry a bit of extra weight in understanding parameterised modules. But they also built a book around it, being the 2nd edition of Real World OCaml, which has been "in progress" for a while now, but definitely isn't empty. – Comprehensible

M.(+) n (f a) might also be M.(n + f a) – Leonhard

Answer 4

Here's a small, self-contained example with first class modules. It implements the polymorphic add function of the original question.

module type Add = sig
  type t
  val add : t -> t -> t
end

module I = struct
  type t = int
  let add = ( + )
end

module F = struct
  type t = float
  let add = ( +. )
end

let add (type a) (module M : Add with type t = a) x y =
  M.add x y

then you can use add like this:

# add (module I) 1 2;;
- : I.t = 3

# add (module F) 1. 2.;;
- : F.t = 3.

Verein

Note that the Int and Float modules in the current standard library could be used in place of your I and F modules. – Leonhard

That's true and a good point. I intentionally made new modules here so that everything is explicit in this example. – Verein