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 LAA28477; Wed, 31 Mar 2004 11:11:54 +0200 (MET DST) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id LAA29256 for ; Wed, 31 Mar 2004 11:11:53 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i2V9Cajq007442 for ; Wed, 31 Mar 2004 11:12:36 +0200 Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.10/jtpda-5.4) with ESMTP id i2V9BnAs075639 ; Wed, 31 Mar 2004 11:11:49 +0200 (CEST) X-Ids: 164 Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id LAA127238 ; Wed, 31 Mar 2004 11:10:22 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id LAA848002 ; Wed, 31 Mar 2004 11:11:36 +0200 X-Authentication-Warning: ibm1.cicrp.jussieu.fr: fernande owned process doing -bs Date: Wed, 31 Mar 2004 11:11:35 +0200 (DST) From: Diego Olivier Fernandez Pons X-X-Sender: fernande@ibm1 To: Jon Harrop cc: caml-list@inria.fr Subject: Re: [Caml-list] Extensible graphs In-Reply-To: <200403282300.57264.jdh30@cam.ac.uk> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at nez-perce by Joe's j-chkmail ("http://j-chkmail.ensmp.fr")! X-Miltered: at shiva.jussieu.fr with ID 406A8B55.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Loop: caml-list@inria.fr X-Spam: no; 0.00; pons:01 pons:01 etu:99 caml-list:01 extensible:01 generic:01 haskell:01 functors:01 char:01 char:01 mytype:01 baire:01 accessors:01 functorial:01 struct:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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