Re: [Caml-list] revised syntax for abstract types ?

[Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>]

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