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

Troublesome nodes
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2008-07-11 (20:39) From: Dario Teixeira Subject: Troublesome nodes
```Hi,

This problem was originally raised in a thread in the ocaml-beginners
list [1], but since polymorphic variants, covariant constraints, and
recursive knots were brought into the discussion, I reckon it deserves
the attention of some heavy weights.  Moreover, the problem is trickier
than first appearances suggest.

So, what's the situation?  I want to create a data structure holding
document nodes.  There are four different kinds of nodes, two of which
are terminals (Text and See), and two of which are defined recursively
(Bold and Mref).  Moreover, both See and Mref produce links, and there
is an additional constraint that a link node may *not* be the immediate
ancestor of another link node.  Using conventional union types, a node
could be modelled like this:

module Old_node =
struct
type seq_t = super_node_t list
and super_node_t =
| Text of string
| Bold of seq_t
| Mref of string * nonlink_node_t list
| See of string
end

The problem with this representation is that it introduces an unwanted
scaffolding for nodes.  Moreover, it prevents the use of constructor
functions for nodes, since non-link nodes may be represented in the
tree in a context-dependent fashion: either directly such as Bold [...],
distinction in the structure is helpful for pattern matching purposes,
but the extra scaffolding is just a pain.

One alternative is to use polymorphic variants, and to take advantage
of the fact that new types can be built as the union of existing ones.
Ideally, one could do something like this:

type seq_t = super_node_t list
[ `Text of string
| `Bold of seq_t ]
[ Mref of string * nonlink_node_t list
| See of string ]

However, this fails with an error "The type constructor nonlink_node_t is
not yet completely defined".  Jon Harrop suggested untying the recursive
knot, but the solution has a few drawbacks of its own [2].

Another alternative is to flatten the structure altogether and to annotate
the constructor functions with phantom types to prevent the violation of
the no-parent constraint:

module Node:
sig
type seq_t = node_t list
and node_t =
private
| Text of string
| Bold of seq_t
| Mref of string * seq_t
| See of string

type +'a t

val text: string -> [> `Nonlink] t
val bold: 'a t list -> [> `Nonlink] t
val mref: string -> [< `Nonlink] t list -> [> `Link] t
val see: string -> [> `Link] t
end =
struct
type seq_t = node_t list
and node_t =
| Text of string
| Bold of seq_t
| Mref of string * seq_t
| See of string

type +'a t = node_t

let text txt = Text txt
let bold inl = Bold inl
let mref ref inl = Mref (ref, inl)
let see ref = See ref
end

even a simple Node_to_Node translator becomes a mess:

module Node_to_Node =
struct
| Node.Text txt          -> Node.text txt
| Node.Bold inl          -> Node.bold (List.map convert_super_node inl)
| _                      -> failwith "oops"

| Node.Mref (ref, inl)   -> Node.mref ref (List.map convert_nonlink_node inl)
| Node.See ref           -> Node.see ref
| _                      -> failwith "oops"

and convert_super_node node = match node with
| Node.Text _
| Node.See _
| Node.Mref _            -> convert_link_node node
end

So, I am looking for a solution that meets the following conditions:

- It satisfies the "no link node shall be parent of another" constraint;
- the structure should be pattern-matchable;
- but nodes should be created via constructor functions.

Any ideas?

Thanks in advance and sorry for the long post!
Cheers,
Dario Teixeira

[1] http://tech.groups.yahoo.com/group/ocaml_beginners/message/9930
[2] http://tech.groups.yahoo.com/group/ocaml_beginners/message/9932

__________________________________________________________