Home     About     Download     Resources     Contact us

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

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 (21:23) From: Daniel_Bünzli Subject: Re: [Caml-list] Encoding existential types without modules
```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 . Applying this solution gives
the following (much simpler and maybe more efficient) code.

Daniel

 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

```