beginner question: DAGs w/ recursive types an encapsulation of a Map

beginner question: DAGs w/ recursive types an encapsulation of a Map

[Justin Corn]

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

Dear all,

I'm trying to construct a tree (for the Aho-Corasick exact match algorithm)
but I can't quite figure out how to do this.

1) Is it possible to declare a recursive type that would allow for a tree
having an arbitrarily large number of children per node?

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

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);;

but then the top level was not happy with

#type node = { a: int; b: CharMap.t };;

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?

Thanks,
Justin

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

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

[Gabriel Kerneis]

[-- 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 --]

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

[Jean-Christophe Filliatre]

 > 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?

There is a (small but portable) graphical library coming with
ocaml. This is the Graphics module, documented in the manual:
http://caml.inria.fr/pub/docs/manual-ocaml/manual039.html

-- 
Jean-Christophe

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

[Pablo Polvorin]

[-- 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 --]

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

[Jon Harrop]

On Sunday 06 May 2007 04:33, Pablo Polvorin wrote:
> 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?

OCaml has a -rectypes option that relaxes type checking and allows more types 
though. This relaxation is usually undesirable because it results in 
obfuscated error messages for some type errors, so -rectypes is off by 
default.

However, you have struck upon a case where it could be useful.

Rather than defining your tree type as:

# type tree = Node of int * (char * tree) list ;;
type tree = Node of int * (char * tree) list

with -rectypes you can define it as:

# type tree' =  int  * (char * tree') list ;;
type tree' = int * (char * tree') list

This is not "unsafe" in the usual sense of the word but it means that the 
compiler will be less friendly on all of the rest of your code. Also, I have 
had the OCaml compilers crash in the past if you try to mix code compiled 
with -rectypes with code without.

Another solution is to use polymorphic variants:

# let rec tree = `Node(3, ['a', tree]);;
val tree : [> `Node of int * (char * 'a) list ] as 'a = ...

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?e

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

[Alain Frisch]

Jon Harrop wrote:
> # type tree' =  int  * (char * tree') list ;;
> type tree' = int * (char * tree') list
> 
> This is not "unsafe" in the usual sense of the word but it means that the 
> compiler will be less friendly on all of the rest of your code. 

The declaration is not "unsafe" by itself, but the -rectypes option is,
in the sense that it will make the compiler accept programs that will
produce infinite loops in the run-time system:

http://caml.inria.fr/pub/docs/manual-ocaml/libref/Lazy.html

<< Note: if the program is compiled with the -rectypes option,
ill-founded recursive definitions of the form let rec x = lazy x  or let
rec x = lazy(lazy(...(lazy x))) are accepted by the type-checker and
lead, when forced, to ill-formed values that trigger infinite loops in
the garbage collector and other parts of the run-time system. Without
the -rectypes option, such ill-founded recursive definitions are
rejected by the type-checker. >>

(One might argue that the type checker does not reject non-terminating
programs anyway.)

-- Alain

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

[skaller]

On Sun, 2007-05-06 at 09:54 +0200, Alain Frisch wrote:
> Jon Harrop wrote:

> << Note: if the program is compiled with the -rectypes option,
> ill-founded recursive definitions of the form let rec x = lazy x  or let
> rec x = lazy(lazy(...(lazy x))) are accepted by the type-checker and
> lead, when forced, to ill-formed values that trigger infinite loops in
> the garbage collector and other parts of the run-time system. 

I'm curious how this can happen to the garbage collector?

Recursive routines that don't maintain a visitation trace
I can understand failing .. but surely the GC has to deal
with cycles anyhow.. I mean the whole *point* of a garbage
collector is to deal with cyclic data .. :)


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net