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

As an addendum to Jeffrey Scofield's answer, we might abstract out this behavior with an adaptation of scanl from Haskell. This scan_left function is generally applicable.

let rec scan_left f i = function
  | [] -> [i]
  | x::xs -> i :: scan_left f (f i x) xs

This can still be tail-recursive with tail_mod_cons.

let[@tail_mod_cons] rec scan_left f i = function
  | [] -> [i]
  | x::xs -> i :: scan_left f (f i x) xs

Now we can implement partialsums as essentially a specialization of scan_left.

let partialsums plus = function
  | [] -> []
  | x::xs -> scan_left plus x xs

Or using first class modules.

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

let partialsums (type a) (module M : Addable with type t = a) = function
  | [] -> []
  | x::xs -> scan_left M.add x xs

Answer 2

With first-class modules, yes.

Edit: Updated this answer with references to the better answers in this thread.

The right answer today is to use first-class modules:

(Introduced in OCaml 3.12; pattern syntax and package type inference introduced in 4.00; structural comparison of package types introduced in 4.02.; fewer parens required starting from 4.05)

This is demonstrated in two other answers more recent than this one:

• neo's answer shows how to do this using Jane Street's Base library.
• mndrix's answer shows how to do this in a self-contained example using plain OCaml.

With parametric polymorphism, no.

There is no supertype between int and float that supports addition.

With ad-hoc polymorphism, yes.

Edit: This answer only has historic value.

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!

Edit: This answer only has historic value.

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 3

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.

Answer 4

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

Answer 5

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