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

Induction over types
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2008-02-01 (21:31) From: Christophe TROESTLER Subject: Re: [Caml-list] Induction over types
```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

```