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

revised syntax for abstract types ?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2009-12-11 (00:18) From: Jacques Garrigue Subject: Re: [Caml-list] revised syntax for abstract types ?
```From: Serge Leblanc <serge.leblanc@orange.fr>
> In the following types definitions,
>
> type trie 'a = [ Trie of arcs 'a ]
> and arcs 'a = list ('a * trie 'a);
>
> type zipper 'a = [ Top | Zip of (arcs 'a * 'a * arcs 'a * zipper 'a) ]
> and edit_state 'a = (zipper 'a * trie 'a);
>
> why is it not possible to describe them thus ?
>
> type letter = 'a;
> type trie = [ Trie of arcs ]
> and arcs = list (letter * trie);
>
> type zipper = [ Top | Zip of (arcs * letter * arcs * zipper) ]
> and edit_state = (zipper * trie);

Note first that revised syntax is just syntax, it does not change the
semantics. So, translating your question on a simpler example in
standard syntax, how does

type 'a list = Nil | Cons of 'a * 'a list

relate to

type elt
type list = Nil | Cons of elt * list

The answer is that they describe the same data, but in an incompatible
way. The first approach uses ML polymorphism, so that you can build a
list of any given type, letting the type checker choose the element
type.

The second is a signature, and should be used in combination with
functors, the type being chosen explicitly. For instance, you can
write a map function in the following way:

module type List = sig
type elt
type list = Nil | Cons of elt * list
end
module F(T:List) = struct
open T
let rec map f = function
Nil -> Nil
| Cons (h,t) -> Cons (f h, map f t)
end

module IntList = struct
type elt = int
type list = Nil | Cons of elt * list
end
module IntM = F(IntList);;

IntM.map succ (IntList.Cons (1, IntList.Nil));;

Again, these two definitions of list, while representing the same data,
are incompatible.

Hope this helps.

Jacques Garrigue

```