ocaml - Existentially quantified type parameter, recursive function and type error -

consider following piece of ocaml code:

type mytype = : 'a list * 'a -> mytype  let rec foo : int -> mytype =     fun n -> if n < 0 my([], 2)         else let my(xs, y) = foo (n - 1)         in my(3::xs, y) 

the ocaml interpreter gives me error on last line of foo, saying:

this expression has type a#1 list expression expected of type int list

type a#1 not compatible type int

i make code work adding type parameter mytype be

type _ mytype = : 'a list * 'a -> 'a mytype let rec foo : int -> 'a mytype = ... 

but let's don't want change definition of mytype. write foo, assuming want preserve function's (intuitively understood non-working code) behaviour?

also, explain root of problem, i.e. why initial code doesn't type-check?

when pattern matching done on mytype value, there no way know type inside. thing is, typing system acts quite , doesn't try know mytype if comes recursive call (the typing system doesn't work way).

the thing is, know in case 'a indeed int, need give proof of compiler.

in specific case, don't need to. need use gadt @ end of function:

let foo n =  let rec aux n =   if n < 0 ([], 2)   else let (xs, y) = aux (n - 1)    in (3::xs, y)  in  let (xs,y) = aux n in (xs,y) 

it worth noting type definition, there no way use fact know there integers values in mytype, pretty unusable. gadts should used in specific cases , should precisely know why , how you'll using them.

edit:

a type can seen logical formula attached every value. in cases, pretty simple , don't have worry it, because type variables ('a 'b , forth) universally quantified , visible exterior of type.

type 'a mylist = cons of 'a * 'a list | nil (* should read as:     'a,     'a mylist either       * cons containing same 'a , 'a list       * nil *)  type mylist = cons : 'a * mylist -> mylist | nil : mylist (* should read as:     mylist either      * 'a, 'a , list      * nil *) 

in gadt above, can see nothing states every element in list of same type. in fact, if mylist, have no way of knowing element inside.

so, need prove it. way of doing store inside gadt proof of type:

type _ proof =  | int : int proof  | float : float proof  | tuple : 'a proof * 'b proof -> ('a * 'b) proof  (* can add other constructors depending on     types want store *)  type mytype = : 'a proof * 'a list * 'a -> mytype 

now this, when opening mytype, can match on proof prove value of 'a. compiler know it's same because refuse create mytype without proof corresponding right type.

as can see, gadts not simple, , need several drafts before going implementation. of time, can avoid using them (and if you're not sure of how work, don't use them @ all).