Why this function has weak type when i use function keyword? OCaml

user_13249640 0
Viewed 66
let duplicates =
  let rec duplicates' accumulator = function
    | [] -> accumulator
    | [ item ] -> duplicates' (item :: accumulator) []
    | item :: item2 :: tail ->
      if item = item2 then duplicates' (item :: accumulator) tail
      else duplicates' (item::accumulator) (item2::tail)
  in
  duplicates' [];;

If I add a second parameter that must be a 'a list and use "match with" on it the code works.

(also: the end of codes and with: in duplicates [] 'parameter')

If I use function keyword and make the code more concise, the function returns:

val duplicates : '_weak14 list -> '_weak14 list = <fun>
ocaml functional-programming
1 Answers

This is the value restriction. Your function duplicates is defined not by a value (i.e., a lambda) but as an application: duplicates' []. So it can't be generalized.

You can fix this using eta expansion:

# let duplicates list =
  let rec duplicates' accumulator = function
    | [] -> accumulator
    | [ item ] -> duplicates' (item :: accumulator) []
    | item :: item2 :: tail ->
      if item = item2 then duplicates' (item :: accumulator) tail
      else duplicates' (item::accumulator) (item2::tail)
  in
  duplicates' [] list ;;
val duplicates : 'a list -> 'a list = <fun>
#

This works because duplicates is now defined as a lambda using the compact notation let f x = e, equivalent to let f = fun x -> e.

The value restriction is documented in Section 6 of the OCaml manual, "Polymorphism and its limitations."

I've found the following paper extremely helpful in thinking about the value restriction: Garrigue, Jacques; Relaxing the Value Restriction.

user_8216790
Related