[Caml-list] Extensible graphs

[Jon Harrop <jdh30@cam.ac.uk>]

Hi!

I'm writing code which I wish to sell in object form and I'd like it to 
contain a basic representation of a graph which can be extended. This basic 
graph might be something like:

type leaf = A | B
type node = Leaf of leaf | Group of node list

I'll be defining a bunch of functions which act on a graph, e.g.:

let rec leaf_count n = match n with
  Leaf _ -> 1
| Group l -> List.fold_left (+) 0 (List.map leaf_count l)

People who use this code are likely to want to make a slightly more 
complicated graph which contains, say, an extra leaf type, an extra node type 
and more functions which act on the new type of graph, equivalent to this:

type leaf = A | B | C
type node = Leaf of leaf | FunkyGroup of node list | Group of node list

Adding new functions which use the existing data types is easy, but I can't 
see any way to allow them to add new node types without requiring them to 
reimplement everything, or at least explicitly call the old routines from any 
new ones when they are used with the old data types.

I've also tried using inheritance by deriving everything from an ABC "node". 
But this just replaces this problem with another problem. If the types of 
node are all derived from a "node" ABC then you can easily add new types but 
you can't easily add new (method) functions to all types.

Is factoring out as much code as possible the best I can do, or is there a 
better way to approach this problem?

Cheers,
Jon.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners