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

[Gabriel Kerneis <gabriel.kerneis@enst.fr>]

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

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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 189 bytes --]