Re: [Caml-list] Troublesome nodes

[Dario Teixeira <darioteixeira@yahoo.com>]

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 =
        | Nonlink_node of nonlink_node_t
        | Link_node of link_node_t
    and nonlink_node_t =
        | Text of string
        | Bold of super_node_t list
    and link_node_t =
        | 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 :>
to promote link/nonlink nodes to supernodes:

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
to cast link/nonlink nodes to supernodes:

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



      __________________________________________________________
Not happy with your email address?.
Get the one you really want - millions of new email addresses available now at Yahoo! http://uk.docs.yahoo.com/ymail/new.html