From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id DAA31309; Wed, 7 Apr 2004 03:26:29 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id DAA31267 for ; Wed, 7 Apr 2004 03:26:28 +0200 (MET DST) Received: from ptb-relay02.plus.net (ptb-relay02.plus.net [212.159.14.213]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i371QRYM026287 for ; Wed, 7 Apr 2004 03:26:27 +0200 Received: from [80.229.56.224] (helo=chetara) by ptb-relay02.plus.net with esmtp (Exim) id 1BB1pj-000EOs-99 for caml-list@inria.fr; Wed, 07 Apr 2004 01:26:27 +0000 From: Jon Harrop Organization: University of Cambridge To: caml-list@inria.fr Subject: Re: [Caml-list] Extensible graphs Date: Wed, 7 Apr 2004 02:26:36 +0100 User-Agent: KMail/1.5.4 References: In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200404070226.36673.jdh30@cam.ac.uk> X-Miltered: at concorde by Joe's j-chkmail ("http://j-chkmail.ensmp.fr")! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 extensible:01 extensible:01 generic:01 reuse:01 iterator:01 implemented:01 generic:01 font:99 glyph:01 renders:01 overlay:01 ugliness:01 val:01 unit-:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk X-Status: X-Keywords: X-UID: 84 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