'a Set?

'a Set?

[Mike Hamburg]

Is there any clean way to make a type 'a set, corresponding to Set.Make 
of a module with type t='a and compare=Pervasives.compare?  I'm trying 
to make a module which uses sets of arbitrary types of objects, and I 
don't want to have to make it a functor.

So in other words, I'd like to make a module AlphaSet with type
type 'a t,
val is_empty: 'a t -> bool
val mem: 'a -> 'a t -> bool,
etc.

instead of Set which is a functor producing
types t, elt
val is_empty: t -> bool
val mem: elt -> t -> bool,
etc.

Is there a clean way to do this without removing the code from set.ml 
and modifying it?

Mike Hamburg

Re: [Caml-list] 'a Set?

[Jean-Christophe Filliatre]

Mike Hamburg writes:
 > Is there any clean way to make a type 'a set, corresponding to Set.Make 
 > of a module with type t='a and compare=Pervasives.compare?  I'm trying 
 > to make a module which uses sets of arbitrary types of objects, and I 
 > don't want to have to make it a functor.

This is a recurrent question on this list.

 > Is there a clean way to do this without removing the code from set.ml 
 > and modifying it?

Unfortunately, no. 

Note that when duplicating the code from set.ml, you can either keep a
functorized code, with an additional type parameter:

  module type OrderedType = sig
    type 'a t
    val compare: 'a t -> 'a t -> int
  end
  module type S = sig
    type 'a elt
    type 'a t
    ...
  end
  module Make(Ord: OrderedType): (S with type 'a elt = 'a Ord.t)

or directly substitute  Pervasives.compare for the comparison function
to get a polymorphic data structure (and no functor anymore):

  module AlphaSet : sig
    type 'a elt
    type 'a t
    ...
  end

Best regards,
-- 
Jean-Christophe

Re: [Caml-list] 'a Set?

[Frédéric Gava]

Hi

> Mike Hamburg writes:
>  > Is there any clean way to make a type 'a set, corresponding to Set.Make
>  > of a module with type t='a and compare=Pervasives.compare?  I'm trying
>  > to make a module which uses sets of arbitrary types of objects, and I
>  > don't want to have to make it a functor.
>
> This is a recurrent question on this list.
>
>  > Is there a clean way to do this without removing the code from set.ml
>  > and modifying it?
>
> Unfortunately, no.
> Note that when duplicating the code from set.ml, you can either keep a
> functorized code, with an additional type parameter:

I think this problem comes from the stdlib of OCaml. We have:
1) For the Hashtable
 type ('a, 'b) t
and
val length : ('a, 'b) t -> int
and
module type S = sig
 type key
 type 'a t
  .... end
 2) For the Map
module type S = sig
  type key
  type +'a t
end
3) For the Set
module type S = sig
  type elt
  type t
val cardinal : t -> int
end

This is hard to understand why the signatures of those modules are so
differents. Why there is (for example) not for the set, this signature:
module type S = sig
    type 'a elt
    type 'a t
    ...
  end ?
Furthermore there is no lenght/cardinal function for the Map. Note that
WeakHashtble have the function val count : t -> int, so three different
names for the same things. When I teach Ocaml, many students are lost with
this differences.

Best regards,
Frédéric Gava

Re: [Caml-list] 'a Set?

[Radu Grigore]

On Wed, 26 Jan 2005 11:13:58 +0100, Frédéric Gava
<frederic.gava@wanadoo.fr> wrote:
> When I teach Ocaml, many students are lost with
> this differences.

What puzzeled my is that List/String methods take the structure on
which they act as the first parameter while the Set/Map methods take
the structure on which they act as their last parameter. Is there a
reason?

-- 
regards,
 radu
http://rgrig.idilis.ro/

Re: [Caml-list] 'a Set?

[Jacques Garrigue]

From: Radu Grigore <radugrigore@gmail.com>

> On Wed, 26 Jan 2005 11:13:58 +0100, Frédéric Gava
> <frederic.gava@wanadoo.fr> wrote:
> > When I teach Ocaml, many students are lost with
> > this differences.
> 
> What puzzeled my is that List/String methods take the structure on
> which they act as the first parameter while the Set/Map methods take
> the structure on which they act as their last parameter. Is there a
> reason?

There seems to be an habit of having side-effecting functions take
their "object" as first parameter, while side-effect-free functions
take them as last.

One reason is that it is natural to specialize side-effecting function
on their "object", as it doesn't change (only its contents do), while
effect-free functions are best seen as transforming their object
(which should be last).

If you respect this convention, the type tells you about the semantics
:-)

Jacques Garrigue

Re: [Caml-list] 'a Set?

[Alex Baretta]

Jacques Garrigue wrote:
> From: Radu Grigore <radugrigore@gmail.com>

> If you respect this convention, the type tells you about the semantics
> :-)

There are two different patterns for function signatures: the Hashtbl 
pattern and the Map pattern. Both are "good", depending on the context. 
Since I need both approaches I have come up with a little trick to get 
the best of both worlds.

# let (~%) f = fun x y -> f y x

The ~% operator swaps the first and the second parameter in a function 
call. The following is a trivial example of its use.

# ~% Printf.kprintf "Hello %s!" failwith "World";;
Exception: Failure "Hello World!".

Alex

-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>

RE: [Caml-list] 'a Set?

[Jacques Carette]

This (~%) operator is called 'flip' in Haskell, and it is used there all the
time.  It is kind-of surprising that flip is not in Pervasives [as has been
mentionned before http://caml.inria.fr/archives/200106/msg00093.html].

Jacques

-----Original Message-----
From: caml-list-admin@yquem.inria.fr [mailto:caml-list-admin@yquem.inria.fr]
On Behalf Of Alex Baretta
Sent: January 26, 2005 11:00 AM
To: caml-list@inria.fr
Subject: Re: [Caml-list] 'a Set?


Jacques Garrigue wrote:
> From: Radu Grigore <radugrigore@gmail.com>

> If you respect this convention, the type tells you about the semantics
> :-)

There are two different patterns for function signatures: the Hashtbl 
pattern and the Map pattern. Both are "good", depending on the context. 
Since I need both approaches I have come up with a little trick to get 
the best of both worlds.

# let (~%) f = fun x y -> f y x

The ~% operator swaps the first and the second parameter in a function 
call. The following is a trivial example of its use.

# ~% Printf.kprintf "Hello %s!" failwith "World";;
Exception: Failure "Hello World!".

Alex

Re: [Caml-list] 'a Set?

[Mike Hamburg]

I call this operator <?>, because I often use it like so:

List.map (List.nth <?> 3) myList;;

Sadly, at toplevel <?> makes you lots of pretty '_a that restrict your 
future actions.  See my next post for questions about '_a.

Mike

On Jan 26, 2005, at 11:00 AM, Alex Baretta wrote:

> Jacques Garrigue wrote:
>> From: Radu Grigore <radugrigore@gmail.com>
>
>> If you respect this convention, the type tells you about the semantics
>> :-)
>
> There are two different patterns for function signatures: the Hashtbl 
> pattern and the Map pattern. Both are "good", depending on the 
> context. Since I need both approaches I have come up with a little 
> trick to get the best of both worlds.
>
> # let (~%) f = fun x y -> f y x
>
> The ~% operator swaps the first and the second parameter in a function 
> call. The following is a trivial example of its use.
>
> # ~% Printf.kprintf "Hello %s!" failwith "World";;
> Exception: Failure "Hello World!".
>
> Alex
>
> -- 
> *********************************************************************
> http://www.barettadeit.com/
> Baretta DE&IT
> A division of Baretta SRL
>
> tel. +39 02 370 111 55
> fax. +39 02 370 111 54
>
> Our technology:
>
> The Application System/Xcaml (AS/Xcaml)
> <http://www.asxcaml.org/>
>
> The FreerP Project
> <http://www.freerp.org/>
>
> _______________________________________________
> 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
>

Re: [Caml-list] 'a Set?

[Radu Grigore]

On Wed, 26 Jan 2005 21:04:00 +0900 (JST), Jacques Garrigue
<garrigue@math.nagoya-u.ac.jp> wrote:
> There seems to be an habit of having side-effecting functions take
> their "object" as first parameter, while side-effect-free functions
> take them as last.

This makes sense; but it does not seem to be respected by the standard
library. For example Queue does modifications in place and doesn't
take the queue as the first parameter. Another example is List.nth
which does not have side-effects but takes the list as the first
parameter. And I didn't even tried to look for examples that don't
follow your rule: I was more or less randomly browsing the manual.

> If you respect this convention, the type tells you about the semantics
> :-)

It is a good convention and I'll try follow it. Thanks.

-- 
regards,
 radu
http://rgrig.idilis.ro/

Re: [Caml-list] 'a Set?

[Jon Harrop]

On Tuesday 25 January 2005 23:54, Mike Hamburg wrote:
> Is there a clean way to do this without removing the code from set.ml
> and modifying it?

I do not believe so. I have also had to do this.

Compared to a flat set of functions, the functor approach has the advantage of 
enforcing a consistently used compare function. The same effect can be 
achieved with "elt = 'a" by writing a higher-order function which returns a 
record containing the Set.* functions using the given function argument as 
the compare function. Something equivalent to this:

  type 'a t = 'a list
  type 'a set =
    { empty : 'a t;
      is_empty : 'a t -> bool;
      add : 'a -> 'a t -> 'a t;
      mem : 'a -> 'a t -> bool }

  let rec add compare e = function
    [] -> [e]
  | h :: t -> match compare h e with
      -1 -> e :: h :: t
    | 0 -> e :: t
    | _ -> h :: add compare e t
  let rec mem compare e = function
    [] -> false
  | h :: t -> match compare h e with
      -1 -> false
    | 0 -> true
    | _ -> mem compare e t

  let make ?(compare=compare) () =
    { empty = [];
      is_empty = (fun s -> s=[]);
      add = add compare;
      mem = mem compare }

Possible issues with this are that building closures (i.e. in "make") is 
expensive and that the resulting type is monomorphic ('_a). You can probably 
get a polymorphic type most easily by putting the definitions of "add" etc. 
in the record definition, rather than partially applying their arguments.

Cheers,
Jon.

Re: [Caml-list] 'a Set?

[Frédéric Gava]

Hi,

> Compared to a flat set of functions, the functor approach has the
advantage of
> enforcing a consistently used compare function.
Ok, I am agree.  It is just a remark about coherence of names of functions
and
interfaces of the modules in the stdlib. There is many ModuleName.S
interfaces. Have the same names for functions that have the same semantics
seems (to me) a good things. (for example, have a function cardinal  in the
module Map, even if we could implemented this with a fold; the cardinal
function of the Sets are could also be implemented with a fold)

>The same effect can be
> achieved with "elt = 'a" by writing a higher-order function which returns
a
> record containing the Set.* functions using the given function argument as
> the compare function. Something equivalent to this:
>
>   type 'a t = 'a list
>....
> Cheers,
> Jon.
Ok. I am also agree. But the complexity is the problem of this data
structure ;-)

Cheers,
Frédéric Gava

Re: [Caml-list] 'a Set?

[Jon Harrop]

On Wednesday 26 January 2005 15:36, Frédéric Gava wrote:
> ...
> Ok, I am agree.  It is just a remark about coherence of names of functions
> and
> interfaces of the modules in the stdlib. There is many ModuleName.S
> interfaces. Have the same names for functions that have the same semantics
> seems (to me) a good things. (for example, have a function cardinal  in the
> module Map, even if we could implemented this with a fold; the cardinal
> function of the Sets are could also be implemented with a fold)

There are several problems with this. Firstly, the name "cardinal". A set has 
cardinality. Lists and arrays have length. In C++ the equivalent function is 
"size". Should a map use one of those names or something else (is a map a 
_set_ of mappings? => "cardinal").

Secondly, there are numerous variants on a theme here. You suggest 
implementing Map.cardinal with a fold => O(n). This may be the best that can 
be done at the moment (assuming the internal representation stores maximum 
depth but not number of elements) but by storing the number of elements in 
all branches you could have O(1) "cardinal". Of course, there are other 
variants too (e.g. min = max = d depth => 2^d - 1 elements).

Ultimately, the core library is maintained by INRIA who can ill-afford to 
expend man-hours on adding arbitrary functionality to the core library. I 
would love to see such inclusions (and many others).

Perhaps I should make a webpage listing useful things for people to dabble 
on. :-)

Cheers,
Jon.

Re: 'a Set?

[Jeff Shaw]

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

Mike,
I know of no way to do what you're asking for. However, you can always use lists as an ad hoc kind of set. Use List.mem to check membership, and some functions to add elements or create a set while looking for duplicates:


    let add n list =
      let rec aux = function
   l::ls when compare l n = 0 -> list
 | l::ls -> aux ls
 | [] -> list @ [n]
      in aux list

    let create list =
      let rec aux accumulator = function
   l::ls -> aux (add l accumulator) ls
 | [] -> accumulator
      in aux [] list

This is terribly inefficient for big sets, but it works. It could be made more efficient by making sure the lists are ordered, etc.

Jeff

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