From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id DB0C3BC69 for ; Sat, 5 May 2007 03:00:15 +0200 (CEST) Received: from smtp4-g19.free.fr (smtp4-g19.free.fr [212.27.42.30]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l4510Fd8025545 for ; Sat, 5 May 2007 03:00:15 +0200 Received: from kerneis.info (kerneis.info [82.224.215.18]) by smtp4-g19.free.fr (Postfix) with ESMTP id 5B767678F3 for ; Sat, 5 May 2007 03:00:15 +0200 (CEST) Received: from localhost ([127.0.0.1] helo=kerneis.info ident=gabriel) by kerneis.info with esmtp (Exim 4.63) (envelope-from ) id 1Hk8d0-0004c9-5K for caml-list@yquem.inria.fr; Sat, 05 May 2007 03:00:02 +0200 Date: Sat, 5 May 2007 02:59:54 +0200 From: Gabriel Kerneis To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] beginner question: DAGs w/ recursive types an encapsulation of a Map Message-ID: <20070505025954.71b5a5b5@kerneis.info> In-Reply-To: References: X-Mailer: Sylpheed-Claws 2.6.0 (GTK+ 2.8.20; i486-pc-linux-gnu) Mime-Version: 1.0 Content-Type: multipart/signed; boundary="Sig_lx3oWhOWXlcqpmiac/m/8dw"; protocol="application/pgp-signature"; micalg=PGP-SHA1 X-Miltered: at concorde with ID 463BD71F.004 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; recursive:01 recursive:01 arbitrarily:01 node:01 node:01 val:01 'ocaml:01 nodes:01 ocaml:01 sig:01 val:01 bool:01 bool:01 iter:01 justin:98 X-Attachments: type="application/pgp-signature" name="signature.asc" name="signature.asc" --Sig_lx3oWhOWXlcqpmiac/m/8dw Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Le Fri, 4 May 2007 16:46:29 -0700, "Justin Corn" a =E9crit : > 1) Is it possible to declare a recursive type that would allow for a > tree having an arbitrarily large number of children per node? Yes.=20 > I couldn't figure that one out, so I was thinking I could use a Map > collection to represent edges. For example, using association lists : # type tree =3D Leaf of int | Node of int * (char * node) list ;; type tree =3D Leaf of int | Node of int * (char * node) list # Node (2,[('a',Leaf 5)]);; - : tree =3D Node (2, [('a', Leaf 5)]) Or even : # type tree' =3D int * (char * tree') list ;; type tree' =3D int * (char * tree') list # let t : tree' =3D (2,[('a',(5,[]))]);; val t : tree' =3D (2, [('a', (5, []))]) The second solution involves recursive types : you must run 'ocaml -rectypes' to use it. It could be unsafe and shouldn't be used unless you're perfectly aware of what you're doing. > 2) How do you wrap a Map in an object or record? In my case the edges > represent single characters, so I started with >=20 > #module CharMap =3D Map.Make(Char);; Good idea : lists are not very efficient, so the solution shown above will be greatly improved using Maps (especially if you've got a large number of edges). =20 > but then the top level was not happy with >=20 > #type node =3D { a: int; b: CharMap.t };; The type constructor CharMap.t expects 1 argument(s), but is here applied to 0 argument(s) Map expects an argument : Char is the type of the key (as you can see on the type, when you create CharMap[1] ), but you must define the type of the values. Here, you want to store nodes, so : #type node =3D { a: int; b: node CharMap.t };; If you prefer a generic node type, you can do :=20 # type 'a node =3D { a: int; b: 'a CharMap.t };; (this is a just an example of how keeping things generic - here, it's totally useless) > 3) If there are preexisting graphical libraries for ocaml, maybe I > should just use those, but after searching a bit I was unable to find > any. Does someone know where I could find one? Depends on what you want to do. Have a look at the Caml Hump [2]. [1]=20 # module CharMap =3D Map.Make(Char);; module CharMap : sig type key =3D Char.t (*type of the keys =3D Char.t*) type 'a t =3D 'a Map.Make(Char).t (*type of the values relies on 'a*)=20 val empty : 'a t val is_empty : 'a t -> bool val add : key -> 'a -> 'a t -> 'a t val find : key -> 'a t -> 'a val remove : key -> 'a t -> 'a t val mem : key -> 'a t -> bool val iter : (key -> 'a -> unit) -> 'a t -> unit val map : ('a -> 'b) -> 'a t -> 'b t val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool end [2] http://caml.inria.fr/cgi-bin/hump.cgi Regards, --=20 Gabriel Kerneis --Sig_lx3oWhOWXlcqpmiac/m/8dw Content-Type: application/pgp-signature; name=signature.asc Content-Disposition: attachment; filename=signature.asc -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) iD8DBQFGO9cR6a2JmXQu5bYRAn1SAJ9DHmwlrmDIqNAaNa2+NBTDA7Pp9gCgqb7s yY3D59OesyxDmD37JmJW/f0= =CeYm -----END PGP SIGNATURE----- --Sig_lx3oWhOWXlcqpmiac/m/8dw--