What is the meaning of `abstract` in the `interface definition`?

Question

I quite don't understand how the interface thing works in OCaml.

Let's see an example:

---

About the 'a

So what the meaning of 'a here? I mean I understand that when describing the functions, 'a means arbitrary type. Then what's its meaning here? Does it mean arbitrary set?

Also, Why put 'a in front of set?

---

abstract

When explaining this example, Jason Hickey's Introduction to Objective Caml says:

we need to define a polymorphic type of sets ’a set abstractly. That is, in the interface we will declare a type ’a set without giving a definition, preventing other parts of the program from knowing, or depending on, the particular representation of sets we have chosen.

From the above statements, I guess it means in interface definition, we should hide the implementation details. But what details has been hidden?

---

type 'a set = 'a list

In the implementation file, it says type 'a set = 'a list.

What does this do then?

Does it mean this set only takes a list? If it does mean this, will it be necessary to tell this in the interface file, since user of this set should know it takes only list, right?

Answer 1

So what the meaning of 'a here?

This is like parametric polymorphism for functions (in Java it is known as generics) but for types. In this code sets which store ints will have type int set, strings --- string set etc. 'a is in front because it is common OCaml syntax. In revised syntax type variables are written after typenames: like list int or set list int. For more information about different kinds of polymorphism I can recommend you a book Types at programming languages, part V: Polymorphism. If you understand parametric polymorphism for functions I think it will not be difficult to enhance your knowledge for types.

what details has been hidden?

In your ML file, the type 'a set is defined as a list of elements. To search some element in a list, one must iterate through the list and call (=) for every element (this is the way the function List.mem works). AFAIR in OCaml the stdlib sets are implemented as balanced trees and values which are stored in sets should have function compare: t -> t -> int where t is the type of elements stored in the set. However sets can be defined differently and if you look only at abstract types in .mli, then you can only guess how it is implemented in .ml file.

Indeed, in this definition, the type 'a list has been used to implement the type 'a set, but from the interface file, this information is not visible - the hidden part is the fact that the set type is really a list. The way the module has been implemented, and the choice of which information has been made available to the external world, make it possible for a program to use the set type without knowing how it's made.

It's an important feature of software design, since it let the developer change the implementation of that module without having to change the code that uses it. Making the type abstract enforces that separation: you will get a type error if you try to use a list as a set outside the module.

type 'a set = 'a list

AFAIR, this line introduces a 'type synonym' (or alias) saying: here and below the type set is the same as list and you can use set with functions which expect list and vice versa.

When you see 'a set you should understand that it is just a set of something, when you put a string to set then it will be a string set. If you see 'a set you can't say what is stored or will be stored in this set, but if you see string set, you can. Type synonyms are also mentioned in the book above.

P.S.

So you mean type 'a set = 'a list indicates that the set is expecting list as parameters?

No, it doesn't. You just add new type alias in this line. It doesn't shrink a number of types which can be substituted to 'a type variable. If you write

# type 'a set = 'a list;;
type 'a set = 'a list
# let create x : _ set = [x];;
val create : 'a -> 'a set = <fun>

and then

List.map ((+)1) (create 2);;

the compiler will infer the type of create 2 as an int set (since an int value is used for the parameter of type 'a of create, and the return type of that function is 'a set), then it will look at its table of type aliases (synonyms) and when it will understand that type set is the same as type list it will continue the type inference's process.

You should understand that you should write the right number of type variables when creating a new synonym, i.e. type 'a new_t = ('a*'b) list doesn't make any sense both for me and the compiler. There should be at least as many type variables in the left as in the right: type ('a, 'b) new_t = ('a * 'b) list, for example, works.