Taking apart high level function type definition

Learning
#1

Hello, dear friends!
I am VERY new to Ocaml and struggle through its syntax.
Here are two functions:

let rec fact n = if n < 2 then 1 else n * fact(n-1) ; ;

val fact : int → int =

let succ x = x+1 ; ;

val succ : int → int =

That is easy: int in , int out.

But there is more:

let compose f g x = f(g x) ; ;

val compose : (’a → ’b) → (’c → ’a) → ’c → ’b =

compose fact succ 8 ; ;

  • : int = 362880

I read it like this: "Function “compose” receives three arguments: two functions “f” and “g” and an integer(or any numeric type) “x”.
First we apply “succ” to x and then apply “fact” to the result of that application.
So, we go from left to right, because it is application and it is right associated.
When it comes to the type of the function provided by the REPL, we go the other direction, right to left, and I read it like this:
('a → 'b) is the first function applied, in this case “succ”. It recives “a” and returns (b). We keep them in parenthesis to show that is one function.
('c → 'a) is the second function, “fact”, applied to whatever ('a ->'b) passes on to it. It receives type c and produces an “a”, again? And “c” is what “succ” passed to it?
Then somehow whatever “fact” produced becomes a “c” and is returnd as “b”.
So, as you can see, i am totally lost when it comes to deciphering that function’s type (i mean “compose”).
Could somebody be so kind and LITERALLY take apart this type definition: and explain the flow of information and why a, b, c, a, c, and b are used and in this particular order?

Thanks a lot in advance!!!

#2

Hi, you are almost there, but you need to take the ordering a bit more literally. I.e.,

val compose : ('a -> 'b) -> ('c -> 'a) -> 'c ->     'b
    compose         fact          succ     8  = 362880

Or if you substitute the formal parameters with the callsite arguments:

let compose    f    g x =    f (   g x)
    compose fact succ 8 = fact (succ 8)

Does this make sense?

1 Like
#3

Thanks a lot for such quick reply!
It kind of does make sense but I still want to make sure about couple of things:
" 'b" is a return value of “fact” and at the same time of “compose”, right?
Because return value of “compose” IS return value of “fact”, since “compose” does not really do anything except for combining “succ” and “fact”.
“succ” returns “'a”, which is fed into “fact” and “c” is fed into “succ”.
am I correctly reading all this?

If so, what still confuses me is the direction of the “flow” of this whole thing, it is so counter intuitive…
I would make it look like this:
('c → 'a) → ('a → 'b) → 'b
8 into succ 9 into fact 362880
But I guess it is lambda calculus rules, or something like that, right?

And one last thing: in a manual it says:
Objective Caml’s type printer renames the type parameters encountered;
the first is called ’a, the second ’b and so forth.
So, from what i see in the line like this:
val compose : ('a → 'b) → ('c → 'a) → 'c → 'b
'c is actually the first parameter, so why is it " 'c" and not “a”? How do we count the order?
Thanks again!

#4

The way the compose function is defined is really more from mathematics. I wouldn’t call it high school math exactly, but not much more difficult than that. Mathematically speaking, the composition of two functions f and g is: g · f, such that (g · f)(x) = g(f(x)). The ‘dot’ operator in math is composition of two functions.

I suspect part of the confusion in your code may come from the way it swaps the names of the functions but keeps their ordering. If I were to define it in OCaml, I would do:

let compose g f x = g (f x)

This makes it a bit more clear, I think, because the alphabetical ordering of the function names corresponds to the order of application of the functions–it’s a mnemonic.

The compiler indeed picks whatever convenient type parameter names it wants, if you let it infer the types. E.g.:

val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b

You need to work through the types by substituting them one by one to get the hang of it. E.g.,

fact : 'a -> 'b
succ : 'c -> 'a
8 : 'c

The unification process is a bit like solving a puzzle. Once you do it by hand, you get the feel for it and understand and trust the compiler to do it automatically.

Notice above how the data flow is backwards. 8 : 'c, then succ : 'c -> 'a, then fact : 'a -> 'b, then finally the entire thing returns 'b. In practical OCaml we actually usually don’t use compose to combine functions together. It’s more usual to use the ‘reverse application’ (pipe) operator: 8 |> succ |> fact. The pipe operator is available by default, and it makes it easier to perceive the data flow in left-to-right order.

1 Like
#5

Thank you so much for your help! :slight_smile: :smiley:
Now it makes much more sense!
So, I guess it is all down to practice.