Re: [Caml-list] beginner question: DAGs w/ recursive types an encapsulation of a Map

["Pablo Polvorin" <pablo.polvorin@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 3890 bytes --]

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 some
post related to this topic.. but fail to fully understand 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 écrit :
> > 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 = Leaf of int | Node of int * (char * node) list ;;
> type tree = Leaf of int | Node of int * (char * node) list
> # Node (2,[('a',Leaf 5)]);;
> - : tree = Node (2, [('a', Leaf 5)])
>
> Or even :
>
> # type tree' =  int  * (char * tree') list ;;
> type tree' = int * (char * tree') list
> # let t : tree' = (2,[('a',(5,[]))]);;
> val t : tree' = (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 = 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 = { 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 = { a: int; b: node CharMap.t };;
>
> If you prefer a generic node type, you can do :
> # type 'a node = { 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 = Map.Make(Char);;
> module CharMap :
>   sig
>     type key = Char.t               (*type of the keys = Char.t*)
>     type 'a t = '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
>
>
>


-- 
Pablo Polvorin

[-- Attachment #2: Type: text/html, Size: 5880 bytes --]