Annotated trees

Annotated trees

[Daniel Bünzli]

Hello,

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. ?

Thanks in advance,

Daniel

Re: [Caml-list] Annotated trees

[Martin Jambon]

Daniel Bünzli wrote:
> Hello,
> 
> 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. ?

I normally use the second form.

I see the following advantages over the tuple form:

1. Pattern-matching is more readable because the most important piece of
information comes first:

   `Leaf (_, s) -> ...
 | `Node (_, l) -> ...

instead of:

   (_, `Leaf s) -> ...
 | (_, `Node l) -> ...


2. If needed, writing an annotation_of_t function instead of just using fst is
simple enough and not invasive.

3. It is possible to not annotate certain kinds of nodes, or to have different
types of annotations depending on the kind of node.

4. The tuple version feels like there are 2 different definitions of a tree
node, i.e. it is easy to get confused about whether an annotated node (the
pair) or an non-annotated node (second member of the pair) is expected in one
given place.

5. I got this habit and therefore I won't change my mind and reject all
rational arguments against it ;-)



Martin

-- 
http://mjambon.com/

Re: [Caml-list] Annotated trees

[Martin Jambon]

Martin Jambon wrote:
> Daniel Bünzli wrote:
>> Hello,
>>
>> 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. ?
> 
> I normally use the second form.
> 
> I see the following advantages over the tuple form:
> 
> 1. Pattern-matching is more readable because the most important piece of
> information comes first:
> 
>    `Leaf (_, s) -> ...
>  | `Node (_, l) -> ...
> 
> instead of:
> 
>    (_, `Leaf s) -> ...
>  | (_, `Node l) -> ...
> 
> 
> 2. If needed, writing an annotation_of_t function instead of just using fst is
> simple enough and not invasive.
> 
> 3. It is possible to not annotate certain kinds of nodes, or to have different
> types of annotations depending on the kind of node.
> 
> 4. The tuple version feels like there are 2 different definitions of a tree
> node, i.e. it is easy to get confused about whether an annotated node (the
> pair) or an non-annotated node (second member of the pair) is expected in one
> given place.
> 
> 5. I got this habit and therefore I won't change my mind and reject all
> rational arguments against it ;-)

See, I even did not consider the possibility of using:

type 'a t = [ `Leaf of string | `Node of 'a t list ] * 'a


Note that point (4) remains valid and based on real experience.



Martin

-- 
http://mjambon.com/

Re: [Caml-list] Annotated trees

[Jacques Garrigue]

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

Re: [Caml-list] Annotated trees

[Daniel Bünzli]

> 1. Pattern-matching is more readable because the most important piece of
> information comes first:
>
>   `Leaf (_, s) -> ...
>  | `Node (_, l) -> ...
>
> instead of:
>
>   (_, `Leaf s) -> ...
>  | (_, `Node l) -> ...

I'm not sure I agree on this one since in the second case the
parentheses are not needed. And if you put the annotation in the
second component (as you suggest your second message) then we are back
to most important first and without parentheses :

let f = function
| `Leaf s, _ -> ...
| `Node l, _ -> ...

> 3. It is possible to not annotate certain kinds of nodes, or to have different
> types of annotations depending on the kind of node.

That's true and certainly a good argument for the second form if you
already know the type of your annotations and have such needs. However
if you want to keep that polymorphic (the annotation is a convenience
for the client) it results in a type variable per case which becomes
heavy.

> 4. The tuple version feels like there are 2 different definitions of a tree
> node, i.e. it is easy to get confused about whether an annotated node (the
> pair) or an non-annotated node (second member of the pair) is expected in one
> given place.

I can understand that. It's true that it may make you think that you
are able to get a non-annotated value by just dropping the first
component. On the other hand the rule is quite simple, you always work
with pairs, period.

> 5. I got this habit and therefore I won't change my mind and reject all
> rational arguments against it ;-)

Yes, that's mainly a discussion about taste.

Thanks for your comments,

Daniel

Re: [Caml-list] Annotated trees

[blue storm]

On Mon, Jun 7, 2010 at 11:22 AM, Daniel Bünzli
<daniel.buenzli@erratique.ch> wrote:
> That's true and certainly a good argument for the second form if you
> already know the type of your annotations and have such needs. However
> if you want to keep that polymorphic (the annotation is a convenience
> for the client) it results in a type variable per case which becomes
> heavy.

You probably know that already but there is a nice use of object types
as "type-level records" that make that kind of "lots of type
variables" situations tractable :

type 'annot tree =
 | Leaf of 'leaf_annot * string
 | Node of 'node_annot * 'annot tree list
constraint 'annot =
 < leaf : 'leaf_annot;
   node : 'node_annot >