From: Daniel Bünzli <daniel.buenzli@erratique.ch>

> Does anybody have any real world experience in choosing between the
> following two representations for a tree augmented with annotations ?
> 
> type 'a t = 'a * [ `Leaf of string | `Node of 'a t list ]
> type 'a t = [ `Leaf of 'a * string | `Node of 'a * 'a t list ]
> 
> Which one is more convenient to process, pattern match on, makes code
> more readable etc. ?

First, if you have no specific reason to use them, I would avoid
polymorphic variants in this case. They can make debugging trickier.

Concerning annotations, I usually adopt the technique used in the
ocaml compiler: define a wrapper recort type. I.e., this would be

type 'a t = { desc: 'a t_desc ; anno: 'a }
and 'a t_desc = Leaf of string | Node of 'a t list

The main advantage is that you can read the annotation without
pattern-matching.
But I know that many people are happy with the other aproach, so I'm
not sure that it matters that much.

Jacques Garrigue