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-13 (14:32) From: Dario Teixeira Subject: Re: [Caml-list] Troublesome nodes
```Hi,

For the sake of future reference, I'm going to summarise the solution to
the original problem, arrived at thanks to the contribution of various
people in this list (your help was very much appreciated!).  This might
came in handy in the future if you run into a similar problem.

So, we have a document composed of a sequence of 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).  Both See and
Mref produce links, and we want to impose a constraint that no link node
shall be the immediate ancestor of another link node.  An additional
constraint is that nodes must be created via constructor functions.
Finally, the structure should be pattern-matchable, and the distinction
between link/nonlink nodes should be preserved so that Node-to-Node
functions do not require code duplication and/or ugly hacks.

Using conventional variants, the structure can be represented as follows.
Alas, this solution is not compatible with constructor functions and
requires unwanted scaffolding:

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

Below is the solution that was finally obtained.  Nodes are represented
using polymorphic variants, and the module itself is recursive to get
around the "type not fully defined" problem:

module rec Node:
sig
type nonlink_node_t = [ `Text of string | `Bold of Node.super_node_t list ]
type link_node_t = [ `See of string | `Mref of string * nonlink_node_t list ]
type super_node_t = [ nonlink_node_t | link_node_t ]

val text: string -> nonlink_node_t
val bold: [< super_node_t] list -> nonlink_node_t
val see: string -> link_node_t
val mref: string -> nonlink_node_t list -> link_node_t
end =
struct
type nonlink_node_t = [ `Text of string | `Bold of Node.super_node_t list ]
type link_node_t = [ `See of string | `Mref of string * nonlink_node_t list ]
type super_node_t = [ nonlink_node_t | link_node_t ]

let text txt = `Text txt
let bold seq = `Bold (seq :> super_node_t list)
let see ref = `See ref
let mref ref seq = `Mref (ref, seq)
end

If you try it out, you will see that this solution enforces the basic
node constraints.  The values foo1-foo4 are valid, whereas the compiler
won't accept foo5, because a link node is the parent of another:

open Node
let foo1 = text "foo"
let foo2 = bold [text "foo"]
let foo3 = mref "ref" [foo1; foo2]
let foo4 = mref "ref" [bold [see "ref"]]
let foo5 = mref "ref" [see "ref"]

Now, suppose you need to create an Ast-to-Node sets of functions (a likely
scenario if you are building a parser for documents).  The solution is
fairly straightforward, but note the need to use the cast operator :>

module Ast_to_Node =
struct
let rec convert_nonlink_node = function
| Ast.Text txt          -> Node.text txt
| Ast.Bold seq          -> Node.bold (List.map convert_super_node seq)

and convert_link_node = function
| Ast.Mref (ref, seq)   -> Node.mref ref (List.map convert_nonlink_node seq)
| Ast.See ref           -> Node.see ref

and convert_super_node = function
| Ast.Nonlink_node node -> (convert_nonlink_node node :> Node.super_node_t)
| Ast.Link_node node    -> (convert_link_node node :> Node.super_node_t)
end

Finally, another common situation is to build functions to process nodes.
The example below is that of a node-to-node "identity" module.  Again, it
is fairly straightforward, but note the use of the operator # and the need

module Node_to_Node =
struct
open Node

let rec convert_nonlink_node = function
| `Text txt              -> text txt
| `Bold seq              -> bold (List.map convert_super_node seq)

and convert_link_node = function
| `See ref               -> see ref
| `Mref (ref, seq)       -> mref ref (List.map convert_nonlink_node seq)

and convert_super_node = function
| #nonlink_node_t as node -> (convert_nonlink_node node :> super_node_t)
| #link_node_t as node    -> (convert_link_node node :> super_node_t)
end

Best regards,
Dario Teixeira

__________________________________________________________