Version française
Home     About     Download     Resources     Contact us    

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

Browse thread
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-19 (08:43)
From: Dario Teixeira <darioteixeira@y...>
Subject: Re: [Caml-list] Troublesome nodes

> I don't understand your counter-example. In typechecks without any
> problem, even in older versions. May you did cut it down too much?

Perhaps... ;-)  Here is the full code, producing an error in version
"3.11+dev12 Private_abbrevs+natdynlink (2008-02-29)", compiled via GODI:

module rec Node:
    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 ]
    type (+'a, 'b) t = private 'a constraint 'a = [< super_node_t ]

    val text: string -> ([> nonlink_node_t], [> `Basic]) t
    val bold: ([< super_node_t], 'a) t list -> ([> nonlink_node_t], 'a) t
    val see: string -> ([> link_node_t], [> `Basic]) t
    val mref: string -> (nonlink_node_t, 'a) t list -> ([> link_node_t], [> `Complex]) t

    val make_basic: ('a, [< `Basic]) t list -> ('a, [`Basic]) t list
    val make_complex: ('a, [< `Basic | `Complex]) t list -> ('a, [`Complex]) t list
end =
    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 ]
    type (+'a, 'b) t = 'a constraint 'a = [< super_node_t ]

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

    let make_basic n = n
    let make_complex n = n

> By the way, I somehow get the feeling that your solution is
> over-engineered. You shouldn't need all that many constraints.
> I you could find a way to use private rows rather than private
> abbreviations, your code might be much simpler.
> But I'm sorry I couldn't follow the whole discussion on your problem.
> I you could summarize it shortly, with the basic code (without phantom
> types) and the invariants you are trying to enforce, I might try to
> look into it.

Thanks Jacques, I would really appreciate it.  I'm stuck at this point, so
any help is welcome.  Moreover, this is in fact a neat problem, so any Ocaml
hacker should be able to enjoy it.  Here follows a complete description of
the problem, unprejudiced by the current solution.

I have two types of documents, "basic" and "complex".  Both are composed
of a list of nodes.  The difference between them is that complex documents
may use a superset of the kinds of nodes available for basic documents.
Namely, while basic documents may only use "Text", "Bold", and "See" nodes,
complex documents may also use "Mref" nodes in addition to those three.

In total, there are therefore only four different kinds of nodes.  Two of
those, "Text" and "See" are terminal nodes; the other two, "Bold" and "Mref"
are defined via recursion.  There is one additional restriction: "See" and
"Mref" produce links, and links may not be the immediate ancestors of other
links (note that since "See" is a terminal node and cannot therefore be a
parent, in practice this rule is identical to saying that "Mref" may not
the parent of "See").

Disregarding the basic/complex distinction, nodes could be defined as follows:

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

The table below summarises the properties of each node:

Node:	Allowed for:	Definition:	Produces link?
Text	basic/complex	terminal	no
Bold	basic/complex	rec		no
See	basic/complex	terminal	yes
Mref	complex		rec		yes

There is one final, important, requirement.  I want to be able to
pattern-match on nodes from the outside of the module.  To build a
Node-to-Node function, for example.

To conclude, I'll leave you with some sample documents.  Some are valid,
but others are not.  The compiler should catch the latter.

(* valid *)
let doc1 = make_basic
		text "foo";
		bold [text "bar"];
		see "ref"

(* valid *)
let doc2 = make_complex
		text "foo";
		bold [text "bar"];
		see "ref"

(* valid *)
let doc3 = make_complex
		text "foo";
		mref "ref" [text "bar"]

(* Invalid because a link node is the parent of another *)
let doc4 = make_complex
		mref "ref" [see "foo"]

(* Invalid because basic documents do not allow Mref nodes *)
let doc5 = make_basic
		text "foo";
		mref "ref" [text "bar"]

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!