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?

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.

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 -> ...

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