How does complex type work in ocaml

Learning
1

Hi friends,

I am reading a code snippet which confuses me a lot. I checked the OCaml Syntax for type, but cannot figure out which rule is applied.

So I have a type named state

type state =
  | Decl
  | Init

And I have a module named Symbol, which is used to store variable info, and its definition is

open Core
module T = struct
  type t =
    { name : string [@compare.ignore] [@hash.ignore]
    ; id : int
    }
  [@@deriving compare, hash, sexp]
end
include T
include Comparable.Make (T)

Then there is a record table, storing the whole variable info and their values

type table =
  { vars : state Symbol.Map.t
  ; val : int
  }

My question is

  1. record constructor should be of form below, so state Symbol.Map.t should be a type. But state is a type, and Symbol.Map.t is another type. How can these two combined together without being a tuple?
type <record-name> =
    { <field> : <type>;
      <field> : <type>;
      ...
    }
  1. There is only definition for Symbol.t, but how does Symbol.Map.t come out?
2

Symbol.Map.t is not a type, but a type constructor, basically a mapping from types to types. state Symbol.Map.t means the type obtained by applying the constructor Symbol.Map.t to the type state as argument. In the page you linked, this corresponds to the rule typexpr ::= typexpr typeconstr.

The functor application Comparable.Make(T) returns a structure which includes the module Map within it (see core/core/src/comparable_intf.ml at 4b6635d206f7adcfac8324820d246299d6f572fe ¡ janestreet/core ¡ GitHub). This module Map defines a type constructor Map.t. As this structure is included in Symbol (include Comparable.Make(T)), the end result is that Symbol ends up with a type consturctor Symbol.Map.t.

Cheers,
Nicolas

1 Like
3

In other words, 'a Symbol.Map.t is a generic type with a type parameter 'a, and state Symbol.Map.t is the concrete type of the map after ‘filling in’ the type parameter with the state type.

1 Like
4

In state Symbol.Map.t, state is to Symbol.Map.t the same as in int list, int is to list. list is a type constructor, int is a type, and int list is a type. A type constructor takes a type (or many) as argument and results in a type. It can be considered a function over types that that takes types as arguments and results in a type.

1 Like
5

@nojb @yawaramin @lindig Thank you for your answers!

It makes sense for me to treat state Symbol.Map.t as a legal type obeying the OCaml syntax. But I still get some questions for type constructor.

  1. How can I tell if a type is a generic type (type constructor) or a concrete type? Is type declared in a module without specifying a concrete type (like int, string) generic?

  2. Also, I guess there are some rules for type constructors. It cannot take any type as its argument, right? In this example, why Symbol.Map.t can take state as its argument? I guess its due to [@@deriving compare, hash, sexp], but not quite sure.

I searched type constructor in Real World Ocaml and didn’t find much results, how can I read more about it? :slight_smile: Again, thank you for your helps!

1 Like
6

By looking at the definition: type constructors have parameters, as in type 'a t or type ('a, 'b) t, while plain types do not have any parameters (eg type t). “Plain” types can be considered zero arity type constructors.

Type constructors themselves can take any type as argument. In your example state could be replaced by any type whatsoever. The [@@deriving ...] annotations are there for the “key” type, but for the “value” type (state in your case) there are no restrictions at all.

Cheers,
Nicolas

2 Likes
7

Just to round out the explanation a bit more, in OCaml _ t is also valid syntax for generic types i.e. type constructors. It means ‘t takes a type parameter but I don’t care about its name right now’.

And finally, OCaml also allows a limited form of type constraints on generic type parameters, so you can have something like type 'a t = 'a list constraint 'a = int, which as you can imagine, forces always only the int type as the type parameter here. Constraints are a more advanced technique so their use is more limited.

1 Like