[Caml-list] Extensible graphs

[Caml-list] Extensible graphs

[Jon Harrop]

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

Re: [Caml-list] Extensible graphs

[Diego Olivier Fernandez Pons]

    Bonjour,

> 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

[...]

> 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:

(Please forgive my approximative english and feel free to correct it
whenever needed. Moreover, if some elements seem unclear, do not
hesitate to ask for more explanations)

The problem is the extensibility of graph data structure distributed
in a compiled form. My answer will be two folds :
- generic advice based on my Caml programming experience
- specific advice based on my graph data structure implementation
experience

I have read a few of your web pages and you seem to be an "imperative
programmer" more used to languages such as C++ or Java rather than
functional ones like ML or Haskell.

In "Objective Caml" there is of course "Objective" which states
clearly the language has an object layer but there is still "Caml" and
its functional core. Relevant elements for data structure
implementation are :
- parametric polymorphism
- functors
- polymorphic variants
- private constructors

> 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.

What do you mean by "new node types" ?

If what you need is to allow any type to be a node, then you should
try a polymorphic data structure :

'a graph (where 'a stands for the type of the node)

the you could have
int graph : a graph in which every node contains an integer type
information
(int * char) graph : a graph in which every node contains an integer
and a char data
(int graph) graph : a graph in which every node contains an
int graph data
MyType graph : your own type data in every node

You will find parametric graph data structures in Baire (see the Hump
in the data structure section) and you can easily build your own ones
(e. g. with a parametric map data structure)


If the "node type" requires specific accessors (i.e. if it is a
module) then you should try functorial graphs.

the user code should look like

 module MyNode = struct ... end

 module MyGraph = Graph.Make (MyNode)

You will find an example of functorial graph library in OCamlGraph
(see the Hump, data structures section) even if in this case it is the
whole graph data structure which is abstracted from the (functorial)
graph algorithms.


You may also want to try "private constructors". It is a kind of
intermediate between the completely open types (e.g. int * int) and
"closed" functors. It is a rather new feature and I am not yet totally
confortable with it, therefor I won't say much more.

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

In the example you give, the "node" is not a node of the graph but
a node of the underlying tree that represents the graph : are you
really sure you need that ?

The main problem here is the pattern-matching since the predefined
functions (like count_leaves) based on it do not work any more.

Possible work-around are :

i) pattern-matching simulation via functors

I tried that once for binary trees

type 'a tree = E | N of 'a tree * 'a * 'a tree
type 'a tree2 = E | N of 'a tree2 * 'a * 'a tree2 * int

I didn't want to rewritte all functions like insert, fold, etc. which
do not depend on the extra int information

let rec height = function
  | E -> 0
  | N (l, _, r) -> 1 + max (height l) (height r)

I defined a module TreePatternMatcher

type 'a t
val is_empty : 'a t -> bool
val left_tree : 'a t -> 'a t
val right_tree : 'a t -> 'a t
val value : 'a t -> 'a
val partition : 'a t -> 'a t * 'a * 'a t

then I wrapped all functions in a functor using this interface

let rec height = function tree ->
  if is_empty tree then 0
  else let (l, _, r) = partition tree in
  1 + max (height l) (height right)

ii) polymorphic variants

In the previous case, the problem was "inside a constructor"
  N (l, v, r) against N (l, v, r, _)

If you only need to add patterns, then polymorphic variants could be
what you are looking for. The Caml manual gives a few examples of the
use of variants.

> 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.

The object layer of Caml is in my opinion rather subtle and the only
case I have needed it is for adaptive programming (when a data
structure changes its representation silently)

Instead of writting

type tree =
  | TreeRepresentationOne ...
  | TreeRepresentationTwo ...

let insert x = function
  | TreeRep1 t -> TR1.add x t
  | TreeRep2 t -> TR2.add x t

you use the object layer to downcast to a common subtype.

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

It would be easier if you gave us a more detailled example. Anyway, in
my opinion you should first try simple solutions (polymorphic data
structures).


        Diego Olivier

-------------------
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

Re: [Caml-list] Extensible graphs

[Jon Harrop]

First of all, thank you very much for taking the time to reply!

My context is a graphics library. Since posting, I have created a simple 
implementation of the extensible graph using the polymorphic approach. The 
graph is actually over three types ('a, 'b and 'c, for example ;-) and 
contains leaves, "loners" and groups. Leaves have no children and metadata of 
type 'a, loners have a single child and metadata of type 'b and groups 
contain a list of children and metadata of type 'c.

Currently, I am thinking that, in my particular application, it may be 
satisfactory to just have extensible "loners" and keep leaves and groups 
specialised. I am not yet sure though, so I'm keeping everything generic for 
now.

In order to maximise code reuse, I have factored out a number of algorithms: 
iter (equivalent to List.iter), map (almost equivalent to List.map) and apply 
(like "iter" but only applying the functions on a route through the graph 
specified by an "iterator"). I have implemented these algorithms such that 
they are given four functions which get applied to the leaves, loners, groups 
and elements within groups respectively. I have then created slightly more 
specialised versions of these functions such as "render" which transparently 
performs necessary graphics state changes whilst doing an "iter".

I am now in the process of writing code which uses this generic graph 
representation to create a graph with new types of "loner" characterised by 
different metadata and replacement functions, based upon the generic "iter", 
"map" and "apply". This new code is actually for an editor. It creates a new 
"loner" type for a font glyph and an example of a new function is 
"render_selected" which renders a suitable overlay for when the user has 
selected something.

The main, current ugliness with the code is the rather large types which it 
produces, e.g.:

    val generic_render :
	RenderData.t -> 
	  (RenderData.t -> ('leaf, 'loner, 'group) generic_node -> bool) ->
	    (RenderData.t -> 'leaf -> unit) ->
	      (RenderData.t -> 'loner -> (unit->unit) -> unit) ->
		(RenderData.t -> 'group -> (unit->unit) -> unit) ->
		  (RenderData.t -> int -> ('leaf, 'loner, 'group) generic_node -> 
(unit->unit) -> unit) ->
		    ('leaf, 'loner, 'group) generic_node -> unit

Although this is quite daunting, I haven't had _that_ many problems, but it 
can make bug hunting a little more interesting... ;)

On Wednesday 31 March 2004 10:11 am, Diego Olivier Fernandez Pons wrote:
> Bonjour,

Bonjour!

> I have read a few of your web pages and you seem to be an "imperative
> programmer" more used to languages such as C++ or Java rather than
> functional ones like ML or Haskell.

I certainly am, although I was taught a little ML in my first year as an 
undergrad, so I know a tiny bit of basic theory.

> What do you mean by "new node types" ?

I wish to supply a basic graph type which can contain, say (pedagogical 
example), two types of node which represent triangles and squares 
respectively, but I want a user to be able to create a new graph type which 
also includes pentagon nodes. Obviously, I want them to be able to reuse the 
existing code as efficiently as possible.

> If the "node type" requires specific accessors (i.e. if it is a
> module) then you should try functorial graphs.

What do you mean by a "specific accessor"? Do you mean the equivalent of a 
member function required for a class by an abstract base class?

If so then yes, I do, but I also want the set of required functions to be 
extensible (e.g. the addition of "render_selected" in my editor). I believe 
this requirement makes object orientation (ocaml classes?) unsuitable.

> You will find an example of functorial graph library in OCamlGraph
> (see the Hump, data structures section) even if in this case it is the
> whole graph data structure which is abstracted from the (functorial)
> graph algorithms.

Just reading about it, this may be a good way to reduce the size of those 
types. I could encapsulate a generic graph in a functor which is defined over 
the functions which the generic functions such as "iter" apply as they go. 
The only problem is that, I think, the user is likely to want to create 
several different specialisations of "iter", each of which applies a 
different set of functions for the leaves, groups etc., in which case this 
won't work.

What about just encapsulating the iter function itself in a functor, rather 
than the type of the whole graph?

> > type leaf = A | B | C
> > type node =
> >
> >     | Leaf of leaf
> >     | FunkyGroup of node list
> >     | Group of node list
>
> In the example you give, the "node" is not a node of the graph but
> a node of the underlying tree that represents the graph : are you
> really sure you need that ?

I think I see what you mean. Is this not fixed by my now using:

type ('a, 'b, 'c) node =
  Leaf of 'a
| Loner of 'b * node
| Group of 'c * node list

This may be a confusion caused by my using the word "graph" to refer to what 
is commonly known as the "scene graph" in graphics which is, in this case, 
just a tree. There are some cool things which could potentially be done by 
using a scene graph which is not just a tree but I won't go into these now.

> The main problem here is the pattern-matching since the predefined
> functions (like count_leaves) based on it do not work any more.

Ok, I think that is fixed by my implementation which just ignores the metadata 
if it is only after leaf-/group-ness.

> Possible work-around are :
>
> i) pattern-matching simulation via functors

Ok.

> ii) polymorphic variants
>
> In the previous case, the problem was "inside a constructor"
>   N (l, v, r) against N (l, v, r, _)
>
> If you only need to add patterns, then polymorphic variants could be
> what you are looking for. The Caml manual gives a few examples of the
> use of variants.

Ok, I'll check that out too, thanks.

[Objects]
> you use the object layer to downcast to a common subtype.

Which makes adding new node types easy, but I couldn't figure out how to add 
new member functions. I tried multiple inheritance (with an extra ABC) but 
couldn't get it to work.

> > Is factoring out as much code as possible the best I can do, or is
> > there a better way to approach this problem ?
>
> It would be easier if you gave us a more detailled example. Anyway, in
> my opinion you should first try simple solutions (polymorphic data
> structures).

I hope my more detailed explanation has clarified some points.

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