Chris,

Thanks! This works! There's one tiny little bug in your suggestion. It
should be:

let app_to_mylist f = function Intlist x -> f.listfun x | Strlist x ->
f.listfun x;;

Using pattern matching on the function argument leads right back to
the original type instantiation problem.

Regards,
Chris

On 5/3/07, Chris King <colanderman@gmail.com> wrote:
> 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
>
>