Generic subroutines

Learning
1

I am trying to define generic subroutines but ocaml keeps instantiating them.
Specifically, why does this code fail

let (example: (string * string) list -> (string * int) list -> string list)
  = fun l1 l2 ->
  let (local: (string * 'a) list -> string list) = fun l ->
    l |> List.map (fun (s,_) -> s) in
  [local l1; local l2] |> List.concat;;

let () =
  example [("a","b");("c","d")] [("e",6);("g",8);("i",0)]
  |> List.iter (
         fun str -> Printf.printf ">>> %s\n" str
       );;

File "./test.ml", line 5, characters 19-21:
5 |   [local l1; local l2] |> List.concat
                       ^^
Error: This expression has type (string * int) list
       but an expression was expected of type (string * string) list
       Type int is not compatible with type string

when this one succeeds?

let (local: (string * 'a) list -> string list) = fun l ->
  l |> List.map (fun (s,_) -> s);;
let (example: (string * string) list -> (string * int) list -> string list)
  = fun l1 l2 ->
  [local l1; local l2] |> List.concat;;

let () =
  example [("a","b");("c","d")] [("e",6);("g",8);("i",0)]
  |> List.iter (
         fun str -> Printf.printf ">>> %s\n" str
       );;

>>> a
>>> c
>>> e
>>> g
>>> i
2

The problem is the type annotation: here, the variable 'a is an unification variable scoped to the body of example, not a “forall” variable, and it gets unified with both string and int in the body of example. In other words, by annotating local in this manner you actually keep it from being generalized. If you remove the type annotation the code should typecheck without issues.

If you really want to keep the type annotation, you need to write a “forall” type annotation:

let local: 'a. (string * 'a) list -> string list = fun l ->
  List.map (fun (s, _) -> s) l
in

Cheers,
Nicolas

1 Like
3

The relevant section in the manual. When you put a type annotation like this, it acts as a constraint, as @nojb explained. In that setting, the 'a variable (that you write explicitly) is only generalized when you leave the top-level scope.
So you can either:

  • put an explicit polymorphic annotation 'a. ...
  • or not put any annotation
  • or define local as a toplevel binding that gets generalized on its own
  • or used an anonymous type variable _ which does not suffer from the same restrictions:
let (example: (string * string) list -> (string * int) list -> string list)
    = fun l1 l2 ->
    let (local : (string * _) list -> string list) = fun l ->
      l |> List.map (fun (s,_) -> s) in
    [local l1; local l2] |> List.concat

As a final observation, should you be tempted to simplify the body of local as a partial application:
let local = List.map fst in, the value restriction will kick in, preventing local from being generalized.

let (example: (string * string) list -> (string * int) list -> string list)
    = fun l1 l2 ->
    let (local : (string * _) list -> string list) = List.map fst in
    [local l1; local l2] |> List.concat;;
Error: This expression has type (string * int) list
       but an expression was expected of type (string * string) list
       Type int is not compatible with type string
4

Cool. Thanks folks. :slight_smile: