Version française
Home     About     Download     Resources     Contact us    
Browse thread
Polymorphic recursion
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Loup Vaillant <loup.vaillant@g...>
Subject: Re: [Caml-list] Polymorphic recursion
Thanks, everybody.
Now, does anyone have an idea of the overheads? I can build syntactic
sugar for all three case (using my "not yet build" Lisp syntax), so
which is more efficient?

Classes?
Recursive modules?
Records?

Thanks,
Loup

2007/4/4, Alain Frisch <Alain.Frisch@inria.fr>:
> Jeremy Yallop wrote:
> > Right.  You can write polymorphic-recursive functions if you wrap them
> > in recursive modules, though:
> >
> >   module rec Size : sig val size : 'a seq -> int end = struct
> >     let rec size = function
> >       | Unit -> 0
> >       | Seq (_, b) -> 1 + 2 * Size.size b
> >   end
>
> Note that you don't even need the "rec" in this example, and that the
> same idiom would support mutually recursive functions. To make an
> automatic translation simpler, you can simply "open Size" at the
> beginning of the structure to avoid rewriting self-references in the
> function's body. To support local definitions, you can of course rely on
> local modules:
>
> let rec f : 'a 'b. t = E1 in E2
>
> becomes:
>
> let module X = struct
>   module rec Y : sig val f : t end = struct
>     open Y
>     let f = E1
>   end
>   open Y
>   let v = E2
> end in
> X.v
>
> However, this encoding has an important drawback: you cannot use type
> variables currently in scope in t, E1, E2 (as a consequence, we don't
> need to explicitly quantify over variables in the function prototype,
> the encoding forces all the variables in the function's type to be
> universally quantified). By changing the encoding, you can allow
> references to those type variables in E2:
>
> let f =
>  let module X = struct
>    module rec Y : sig val f : t end = struct
>      open Y
>      let f = E1
>    end
>  end in
>  X.Y.f
> in
> E2
>
>
> -- Alain
>
> _______________________________________________
> 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
>