Re: [Caml-list] wrapping parameterized types

["Chris King" <colanderman@gmail.com>]

On 5/3/07, Christopher L Conway <cconway@cs.nyu.edu> wrote:
> # let app_to_mylist f = function Intlist x -> f x | Strlist x -> f x ;;
> Characters 65-66:
>   let app_to_mylist f = function Intlist x -> f x | Strlist x -> f x ;;
>                                                                    ^
> This expression has type string list but is here used with type int list

The problem is, when O'Caml tries to infer the type of f, it
arbitrarily chooses string list -> 'a and dies when it finds it
applied to an int list.  And although the type you want is 'a list ->
'b, O'Caml certainly won't infer this, since you'd have polymorphic
functions like that popping up every time you made a type mistake
(this is the same reason why non-homogenous lists of objects aren't
automatically coerced to a union of their types).

So you might expect that the following would work:

let app_to_mylist (f: 'a list -> 'b) = function Intlist x -> f x |
Strlist x -> f x ;;

but this doesn't force O'Caml to do anything, it's still free to
refine 'a to int or string.  (Just like how if you write "let x: 'a =
5", x is still an int).

The solution is to use existential types.  In a record, you can tell
O'Caml that a particular function _must_ be polymorphic:

type 'b mylistfun = { listfun: 'a. 'a list -> 'b }

Prefixing f's type with "'a." tells O'Caml that 'a is an existential
type variable, meaning that f must be able to work with any 'a.  Note
that 'a doesn't appear in mylistfun's list of type variables (since it
would make no sense to choose a type for 'a).

So armed with mylistfun, you can rewrite app_to_mylist as:

# let app_to_mylist { listfun = f } = function Intlist x -> f x |
Strlist x -> f x;;
val app_to_mylist : 'a mylistfun -> mylist -> 'a = <fun>

and all is well:

#  app_to_mylist { listfun = List.length } (Intlist [1;2;3]);;
- : int = 3

Unfortunately this trick only works with records and objects, so
you're forced to box up the function before handing it to
app_to_mylist.  (I forget the reason why you can't do this in general
but I'm sure someone else can enlighten us both.)

Hope this helps.

- Chris