Search code examples
functiontypessml

Explaining an SML function and its type


So I have this function:

fn (f,g,x) => g(f(x));

The type of this function is:

('a -> 'b) * ('b -> 'c) * 'a -> 'c

Does the function mean that f represents 'a, g represents 'b, and x represents 'c? Also in that case, how does ('a -> 'b) come about? because does that not mean f -> g?

Apologies if this is an obscure and poorly written question.

Could someone explain to me how the type of that function is calculated?

Thank you.


Solution

  • Here's a diagram that might help:

       ('a -> b') * ('b -> 'c) * 'a  ->   'c
        ^^^^^^^^     ^^^^^^^^     ^     ^^^^^^^
    fn (   f      ,     g      ,  x) => g(f(x));
    

    For any types you want 'a, 'b, and 'c,

    • f takes an 'a and returns a 'b
    • g takes a 'b and returns a 'c
    • x is an 'a.

    And the 'c at the end says that, given those things, our function returns a 'c.

    So how do you get a 'c? Well, since x is an 'a, you can use f to get a 'b:

    x : 'a
    f(x) : 'b
    

    now we have a 'b, and if you give g a 'b it will give you back a 'c:

    g(f(x)) : 'c
    

    and that's how we arrived at the body of the function.