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

["Daniel Bünzli" <daniel.buenzli@epfl.ch>]

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.

Daniel

[1] http://caml.inria.fr/archives/200208/msg00334.html

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)

(* Type to handle the polymorphic recursion of the apply function *)
type poly_rec = { apply : 'a 'b. poly_rec -> ('a, 'b) t -> 'a -> 'b }
let apply' r l x = match l with
| Nil id -> id x
| Cons l ->
     with_packed_list l { bind_list = function h,t -> r.apply r t (h x) }

let poly_rec = { apply = apply' }
let apply l x = apply' poly_rec l x

end

(* Example of use *)
let twice x = 2*x
let double x = (x, x)
let list = Funlist.cons twice (Funlist.cons (( = ) 4) (Funlist.cons 
double Funlist.nil))
let a, b = Funlist.apply list 2

-------------------
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