Re: [Caml-list] Polymorphic recursion

["Till Varoquaux" <till.varoquaux@gmail.com>]

There is indeed an issue with polymorphic recursion. It has been shown
that allowing polymorphic recursion in an ML like language would make
the type inference undecidable. One workaround would be for the
typechecker to use type annotations in some given cases. This is
however not the case in Ocaml: type information are either required or
only useful to debug/document some code/"restrict" the type of a given
variable.

Therefor, if you wish to use polymorphic recursion (yep you can) you
might want to use something where you have to specify the type; this
includes records, objects and recursive modules. So this

type 'a seq = Unit | Seq of ('a * ('a * 'a)seq)

type szRec={f:'a.'a seq -> int};;

let size=
 let rec s =
  {f=function
    | Unit -> 0
    | Seq(_, b) -> 1 + 2 * s.f b}
 in
 s.f

might be what you where yearning for.

Cheers,
Till

On 4/3/07, Loup Vaillant <loup.vaillant@gmail.com> wrote:
> I was reading Okasaki's book, "Purely functionnal data structures",
> and discovered that ML (and Ocaml) doesn't support non uniforms
> function definitions.
>
> So, even if:
>
> (**)
> type 'a seq = Unit | Seq of ('a * ('a * 'a)seq);;
> (**)
>
> is correct,
>
> (**)
> let rec size = fun
>    | Unit -> 0
>    | Seq(_, b) -> 1 + 2 * size b;;
> (**)
>
> is not. Here is the error:
> #
> | Seq(_, b) -> 1 + 2 * size b;;
> This expression (the last 'b') has type seq ('a * 'a) but is here used
> with type seq 'a
> #
>
> Why?
> Can't we design a type system which allow this "size" function?
> Can't we implement non uniform recursive function (efficiently, or at all)?.
>
> I suppose the problem is somewhat difficult, but I can't see where.
>
> Regards,
> Loup Vaillant
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>