On Thu, 31 Jan 2008 22:43:36 +0100, Dirk Thierbach wrote:
> 
> type 'a deep_trie = Inner of 'a | Nest of ('a list) deep_trie
> 
> But to deal with this type, we need what is called polymorphic
> recursion -- inside a recursive definition, the recursive function
> must still have the quantifiers, so it can be used for a different
> type. This can only work if the type is known in advance, and the
> only way to encode this into OCaml at the moment is with a record-type.

Actually, a nice way to do the same and which is much more readable
(at heart, it is the very same solution) is to use recursive modules
(their semantic are not completely fixed but I guess the following
should work even in the future):

module rec Deep : sig
  type 'a trie = Inner of 'a | Nest of ('a list) trie
  val map : ('a -> 'b) -> 'a trie -> 'b trie
  val rev_map : ('a -> 'b) -> 'a trie -> 'b trie
end = struct
  type 'a trie = Inner of 'a | Nest of ('a list) trie
  let map f = function
    | Inner x -> Inner(f x)
    | Nest l -> Nest(Deep.map (List.map f) l)
  let rev_map f = function
    | Inner x -> Inner(f x)
    | Nest l -> Nest(Deep.map (List.rev_map f) l)
end;;

open Deep;;

> let y = Nest (Nest (Inner [[1;2]; [3;4]]))

# Deep.rev_map (fun x -> x) y;;
- : int Deep.trie = Nest (Nest (Inner [[4; 3]; [2; 1]]))

My 0.02¤,
ChriS