Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Encoding existential types without modules
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-01-09 (22:24)
From: brogoff@s...
Subject: Re: [Caml-list] Encoding existential types without modules
On Fri, 9 Jan 2004, [ISO-8859-1] Daniel Bünzli wrote:
> Thanks for your feedback.
> Besides, I would just like to point out that the way I solved the
> problem of polymorphic recursion for the apply function in the example
> of the list of composable function cannot be applied in general.
> A general way to solve the problem of polymorphic recursion was given
> by Brian Rogoff in a previous post [1]. Applying this solution gives
> the following (much simpler and maybe more efficient) code.

I blame Jacques Garrigue for that trick! He is entitled to transfer the blame
to whomever he chooses. ;-)

You may also want to consider using the recursive module feature introduced in
OCaml 3.07 for this too. Unfortunately, you can't (yet, Xavier says he's
working on it)  apply it directly to Funlist on account of your nil. That would
be best, but by wrapping apply I think you can do it like so:

module Funlist : sig

(* The funlist datatype *)
  type ('a, 'b) t

(* Constructors *)
  val nil : ('a, 'a) t
  val cons : ('a -> 'b) -> ('b, 'c) t -> ('a, 'c) t

 (* Applying a value to a composition *)
  val apply : ('a, 'b) t -> 'a -> 'b

 end = struct
(* List of composable functions.

     The intended type expressed by the four types below is :
     type ('a, 'b) t = Nil of ('a -> 'b)
                     | Cons of exists 'c. ('a -> 'c) * ('c, 'b) t
   type ('a, 'b) t = Nil of ('a -> 'b) | Cons of ('a, 'b) packed_list
   and ('a, 'b, 'z) list_scope = { bind_list : 'c. ('a -> 'c) * ('c, 'b) t
                                   -> 'z}
   and ('a, 'b) packed_list = { open_list : 'z. ('a, 'b, 'z) list_scope ->
     'z }

         (* Packing and unpacking lists *)
   let pack_list h t = { open_list = fun scope -> scope.bind_list (h,t) }
   let with_packed_list p e = p.open_list e

 (* Constructors *)
   let nil = Nil(fun x -> x)
   let cons h t = Cons(pack_list h t)

   module rec PolyRec : sig val apply : ('a, 'b) t -> 'a -> 'b end =
       let apply l x =
         match l with
         | Nil id -> id x
         | Cons l ->
           l { bind_list = function h,t -> PolyRec.apply t (h x) }
   let apply = PolyRec.apply


-- Brian

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: