Re: [Caml-list] Encoding existential types without modules

[brogoff@speakeasy.net]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: TEXT/PLAIN; charset=X-UNKNOWN, Size: 2527 bytes --]

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 =
     struct
       let apply l x =
         match l with
         | Nil id -> id x
         | Cons l ->
             with_packed_list
           l { bind_list = function h,t -> PolyRec.apply t (h x) }
     end
   let apply = PolyRec.apply

 end

-- Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners