function without args and return type in OCaml

Question

First of all I usually programming in imperative languaes, that makes me hard to explain certain things. First of all is functions without args, and return types. Example is function that flattens a list:

# let rec flat = function
    [] -> []
    | h :: t -> h @ flat t;;

val flat : 'a list list -> 'a list = <fun>

How OCaml interpreter know that:

1. My function flat need exactly one argument which is "list of lists".
2. Flat returns type is a list. Do the interpreter checks it with [] -> [] line?

Answer 1

let rec flat = function
    [] -> []
    | h :: t -> h @ flat t;;

---

You used function keyword. function is a shortcut for match ... with. So the function you wrote is exactly like

let rec flat l = 
  match l with
      [] -> []
    | h :: t -> h @ flat t

That's why ocaml knows your function has one parameter

---

Your function is recursive. [] -> [] is the basic case and it is also where the function will be stopped. And yes, interpreter checks it with [] -> [].

---

Furthermore, a function must have at least a unit parameter which is () or a normal parameter. If a function does not have anything, it is not a function, instead, it is a variable with a fixed value.

Let's have an example:

let f1 = Random.int 10;

f1 does not have any parameter, even without a () (here () is just like a method in Java without any parameter). Then f1 is a constant value which was generated by the Random. No matter when you call it, f1 will always be fixed.

let f2 () = Random.int 10;

f2 is a function. And each time you call f2(), the Random inside will generate a random in and returns it.

Answer 2

let rec flat = function
    [] -> []
    | h :: t -> h @ flat t;;

Let's go through this a step at a time. The function keyword, as you might expect, gives a function. The basic syntax is function | pat1 -> branch1 | pat2 -> branch2, and what you get is a function of one argument that tries to match that argument against each pattern in turn, and for the first pattern that matches the result is the corresponding branch.

So that's how we know flat is a function. Moreover, we can see that its one argument is matched against [], which is a list. So flat must be a function that takes a list. We see that if the input is [] then the output is [], so it's a function that takes a list and returns a list.

Now let's look at that second pattern. h :: t is a pattern that matches a list and creates two new variable bindings: h is the first element of the list and t is all the rest of the elements. In particular, h has whatever type the elements of the input list have.

If you look at what happens if this pattern match succeeds, h @ flat t, we see the list concatenation operator @ applied to h and flat t. This means that h must be a list, and must be the same kind of list as flat t. So the elements of the input list are lists, and so is the output of the function.

This gives you flat : 'a list list -> 'a list.

To answer your questions directly, flat needs exactly one argument because it is defined with the function keyword and the return values of the branches are values and not functions (if the function branches were also functions, that would meant flat could have two or more arguments). It is a list because the pattern match is against list constructors, and it is a list of lists because h is an element of the list and is used with the @ operator, which requires its arguments to be lists, so the elements of the list are lists.

There are actually three reasons why the return type must be a list:

• In the first branch, a list [] is returned.
• In the second branch, the result of @ is returned, and @ returns lists
• Also in the second branch, flat t is called recursively, and then given as an argument to @. Since it is an argument to @, it must be a list, and so flat must return a list.

The third bullet point is especially interesting, because it shows you that it's not just how you create values that determines their type, but how you use them as well.