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=1.0 required=5.0 tests=AWL,HTML_MESSAGE,SPF_NEUTRAL autolearn=disabled version=3.1.3 Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 38D66BC0A for ; Sun, 6 May 2007 05:33:09 +0200 (CEST) Received: from nz-out-0506.google.com (nz-out-0506.google.com [64.233.162.233]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l463X72r021541 for ; Sun, 6 May 2007 05:33:08 +0200 Received: by nz-out-0506.google.com with SMTP id s1so1293776nze for ; Sat, 05 May 2007 20:33:07 -0700 (PDT) DKIM-Signature: a=rsa-sha1; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:references; b=A7ai5803ZgBufgu4a1uHWVD3W0Dfno8PmzEBSTY7GHUaQyM29NSvEIPm3+oVeDM9NSXCNWmjYsV9v2CRSxOqlQGybnHE4WButqDXZl3v3Haijc0r+CizvlPpbFqFONRlAUFg3Ex32ZcbiKPYTigWDpvLZPlzsLC3wXUE4y+qnqU= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:references; b=UBzOJiJ0lH1RMgP/xQjLlD8FZ9QrA4SzQuvXL7V8kMwyKsr9lg4ilFv/sBvj1Yg3TmlpGtzfuMZEpw7Ox1goUKJ7zEEr5gSokWFGeYR4teHo/N7I8xuJydv+PhJ9Xz/5l1SulHX2ay8/aL0uoH+GS0UkR7Ny7v04dGBalZ8UorE= Received: by 10.114.133.1 with SMTP id g1mr255773wad.1178422387115; Sat, 05 May 2007 20:33:07 -0700 (PDT) Received: by 10.115.59.8 with HTTP; Sat, 5 May 2007 20:33:06 -0700 (PDT) Message-ID: <1ffe809c0705052033p6079116fq2a30f5dd942789aa@mail.gmail.com> Date: Sun, 6 May 2007 05:33:06 +0200 From: "Pablo Polvorin" To: "Gabriel Kerneis" Subject: Re: [Caml-list] beginner question: DAGs w/ recursive types an encapsulation of a Map Cc: caml-list@yquem.inria.fr In-Reply-To: <20070505025954.71b5a5b5@kerneis.info> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_77564_25299918.1178422386893" References: <20070505025954.71b5a5b5@kerneis.info> X-j-chkmail-Score: MSGID : 463D4C74.000 on discorde : j-chkmail score : X : 0/20 1 0.000 -> 1 X-Miltered: at discorde with ID 463D4C74.000 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 beginner's:01 ------=_Part_77564_25299918.1178422386893 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Sorry, may be a stupid question, but i dont get it. What is the difference between the first and second solution that you propose, that make the second less safe?. As far as i understand, both are recursive type declarations. I do read som= e post related to this topic.. but fail to fully understand it. what i missing here? Sorry for the 2007/5/5, Gabriel Kerneis : > > 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. > > > 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 > > > > #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). > > > but then the top level was not happy with > > > > #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 : > # 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] > # 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*) > 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, > -- > Gabriel Kerneis > > > _______________________________________________ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > > > --=20 Pablo Polvorin ------=_Part_77564_25299918.1178422386893 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Sorry, may be a stupid question, but i dont get it.
What is the differe= nce between the first and second solution that you propose, that make the s= econd less safe?.
As far as i understand, both are recursive type declar= ations. I do read some post related to this topic.. but fail to fully under= stand it.
what i missing here?



Sorry for the

2007/5/5, Gabriel Kerneis < gabriel.kerneis@enst.fr>:
Le Fri, 4 May 2007 16:46:29 -0700, "Justin Corn" <justincorn@gmail.com>
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?

Y= es.

> I couldn't figure that one out, so I was thinking I cou= ld use a Map
> collection to represent edges.

For example, usi= ng association lists :
# type tree =3D Leaf of int | Node of int * (char * node) list ;;
ty= pe tree =3D Leaf of int | Node of int * (char * node) list
# Node (2,[(&= #39;a',Leaf 5)]);;
- : tree =3D Node (2, [('a', Leaf 5)])
Or even :

# type tree' =3D  int  * (char * t= ree') 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 'oc= aml
-rectypes' to use it. It could be unsafe and shouldn't be us= ed 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
>> #module CharMap =3D Map.Make(Char);;

Good idea : lists are no= t very efficient, so the solution shown above
will be greatly improved using Maps (especially if you've got a lar= ge
number of edges).

> but then the top level was not happy wi= th
>
> #type node =3D { a: int; b: CharMap.t };;
The type co= nstructor=20 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<= br>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, yo= u can do :
# type 'a node =3D { a: int; b: 'a  CharMap= .t };;
(this is a just an example of how keeping things generic - here, it'stotally useless)

> 3) If there are preexisting graphical librar= ies 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?

D= epends on what you want to do. Have a look at the Caml Hump [2].

[1]
# module CharMap =3D Map.Make(Char);;
module CharMap :
 =  sig
    type key =3D=20 Char.t           &nb= sp;   (*type of the keys =3D Char.t*)
    = type 'a t =3D 'a Map.Make(Char).t (*type of the values relies on &#= 39;a*)
    val empty : 'a t
   = ; val is_empty : 'a t -> bool
    val ad= d : key -> 'a -> 'a t -> 'a t
    val find : key -> 'a t -> 'a
&= nbsp;   val remove : key -> 'a t -> 'a t
&n= bsp;   val mem : key -> 'a t -> bool
 &nbs= p;  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 -> boo= l
  end

[2] http://caml.inria.fr/cgi-bin/hump.cgi

Regards,
--
Gabriel = Kerneis


_______________________________________________
Caml-= list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: <= a href=3D"http://caml.inria.fr" target=3D"_blank" onclick=3D"return top.js.= OpenExtLink(window,event,this)">http://caml.inria.fr
Beginner's = list:=20 http://groups.yah= oo.com/group/ocaml_beginners
Bug reports: http:/= /caml.inria.fr/bin/caml-bugs





--
Pablo Polvorin ------=_Part_77564_25299918.1178422386893--