Adding to a set in Ocaml

Question

I have this fundamental issue in OCaml that has been bugging me for a really long time now. I have pattern match that compares an input from a user and prints out a concatenated string. This works fine but then I need to now add this concatenated string to a set within the pattern match. Each time I try to do this I get the error:

This expression has type SS.t = Set.Make(String).t
   but an expression was expected of type string

I am really new to OCaml and this has taken so many days and I have just not been able to figure it out. The code for the pattern matching is below:

type t = Zero | Pproc of string | Procdef of t * t

module SS = Set.Make(String)
let set2= SS.empty

let concattoset s =
    List.fold_right SS.add [s] set2

let rec poc p = match p with
  | Zero -> concattoset "0"
  | Pproc x -> concattoset x
  | Procdef (p1, p2) -> concattoset((poc p1)^"("^(poc p2)^")")

The error I have is :

Procdef (p1, p2) -> concattoset((poc p1)^"("^(poc p2)^")");;
                                ^^^^^^^^
Error: This expression has type SS.t = Set.Make(String).t
       but an expression was expected of type string

Answer 1

I edited your question but it will be available once it is peer reviewed. Nevertheless, let's answer to your question (by the way, don't say "Thanks!" and try to give an example that can help to reproduce your error.)

So, your code looks like this :

type t = Zero | Pproc of string | Procdef of t * t

module SS = Set.Make(String)
let set2= SS.empty

let concattoset s =
    List.fold_right SS.add [s] set2

let rec poc p = match p with
  | Zero -> concattoset "0"
  | Pproc x -> concattoset x
  | Procdef (p1, p2) -> concattoset((poc p1)^"("^(poc p2)^")")

And the error you have is :

Procdef (p1, p2) -> concattoset((poc p1)^"("^(poc p2)^")");;
                                ^^^^^^^^
Error: This expression has type SS.t = Set.Make(String).t
       but an expression was expected of type string

First of all, a set is immutable so SS.add will return a new set, not unit.

According to this, the type of concattoset is SS.elt -> SS.t then the return type of poc is the same as the type of concattoset "0").

That's because when the compiler tries to type a function with a pattern matching it infers the type according to what is returned by each case of the pattern matching :

let rec poc p = match p with
   | Zero -> concattoset "0"
   | ...

Here, p is of type t because it's matched with Zero and concattoset is of type string -> SS.t so concattoset "0" is of type SS.t then poc is of type t (*the type of p*) -> SS.t (the type returned by concattoset "0".

When you call concattoset ((poc p1) ^ poc p2)), poc p1 is expected to be a string (concattoset : string -> SS.t) but has the typeSS.t(the return type ofpoc p1`) and that's what the compiler told you.

---

An (ugly) idea of the code you could write is this :

type t = Zero | Pproc of string | Procdef of t * t

module SS = Set.Make(String)

let concattoset ?s1 ?sep1 ?sep2 s2 set =
    let str = Printf.sprintf "%s%s%s%s" 
       (match s1 with None -> "" | Some s -> s)
       (match sep1 with None -> "" | Some s -> s)
       s2
       (match sep2 with None -> "" | Some s -> s)
    in
    SS.add str set;;

let rec poc p set = match p with
  | Zero -> concattoset "0" set
  | Pproc x -> concattoset x set
  | Procdef (p1, p2) -> concattoset ~s1:(poc p1) ~sep1:"(" ~sep2:")" (poc p2) set

---

But that's a bit awkward to do and if your types has multiple constructors it will rapidly be hard to write a good concattoset.

What I would do is the following (added Timer for a more complex constructor):

let rec pp fmt = function
  | Zero -> Format.fprintf fmt "0"
  | Pproc x -> Format.fprintf fmt "%s" x
  | Procdef (p1, p2) -> Format.fprintf fmt "%a(%a)" pp p1 pp p2
  | Timer(t,chan, var, p1, p2) -> Format.fprintf fmt "timer%s(%s(%s).%a,%a)" t chan var pp p1 pp p2;;


let concattoset s set = SS.add s set;;

let poc p set = concattoset (Format.asprintf "%a" pp p) set;;

So, pp takes a formatter (which can be seen as an output buffer) a prints in it your constructors with the necessary recursive calls. concattoset is as simple as a SS.add and poc takes a parameter of type t and a set and calls pp with a formatter being a string and gives this new string to concattoset which is exactly what you want to have.

---

About %a :

It may seem a bit strange that pp is expecting 2 arguments but I only give one when I call, for example Format.asprintf "%a" pp p. Well, actually, I'm not applying pp to p, here, I'm giving 2 arguments to the printer like said in the documentation :

a: user-defined printer. Take two arguments and apply the first one to outchan (the current output channel) and to the second argument. The first argument must therefore have type out_channel -> 'b -> unit and the second 'b. The output produced by the function is inserted in the output of fprintf at the current point.

That's why writing Format.asprintf "%a" (pp p) wouldn't be accepted by the compiler.

Answer 2

I can't reproduce your error. When I try an analogous example with a simplified version of your type there is no error.

# let set2 = SS.empty;;
val set2 : SS.t = <abstr>
# let concattoset s = List.fold_right SS.add [s] set2;;
val concattoset : SS.elt -> SS.t = <fun>
# let proc p = match p with
| None -> concattoset "0"
| Some s -> concattoset s;;
val proc : SS.elt option -> SS.t = <fun>
# SS.elements (proc (Some "def"));;
- : SS.elt list = ["def"]

However, it looks to me like you're expecting to be able to treat a set as a mutable container. A set in OCaml is immutable. If you want to build up larger and larger sets, you would want to pass an input set to your function, and have the function add to that set (not to an empty set), and return the result.

Here is a session that might illustrate what it means for sets to be immutable:

# module SS = Set.Make(String);;
module SS : sig ... end
# let s = SS.empty;;
val s : SS.t = <abstr>
# SS.elements s;;
- : SS.elt list = []
# SS.add "abc" s;;
- : SS.t = <abstr>
# SS.elements s;;
- : SS.elt list = []

The expression SS.add "abc" s returns a new set containing the string "abc". It doesn't change s, which is immutable.

In OCaml when you talk about adding a string to a set, it means that you are making a new set that contains the string. The previous set (being immutable) isn't changed.

Here's a function that adds two given strings to a set, and returns the new set:

let add2 set s1 s2 =
    SS.add s1 (SS.add s2 set)

The set parameter is the input set. The result of the function is a new, larger set. The input set is not changed in the process (it is immutable).