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

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

```