CODEWITHSUNDEEP
functiontypessml
Chris
Chris

Reputation: 815

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.

Upvotes: 2

Views: 181

Answers (3)

sshine
sshine

Reputation: 16105

Since the other answers already sufficiently explain how to derive the type for this function, I will just add that if the x argument were instead curried and the composition of f and g flipped, the function would be equivalent to the composition operator that is already built into Standard ML:

  • fn (f, g) => (fn x => f (g x)) is equivalent to
  • fn (f, g) => (fn x => (f o g) x)) is equivalent to
  • fn (f, g) => f o g is equivalent to
  • fn (f, g) => (op o) (f, g) is equivalent to
  • op o.

Upvotes: 1

luqui
luqui

Reputation: 60463

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.

Upvotes: 5

Gilles 'SO- stop being evil'
Gilles 'SO- stop being evil'

Reputation: 107739

The type of a function that maps (x1, x2, x3) to e is τ₁ * τ₂ * τ₃ -> τ' where τ₁ is the type of x1, τ₂ is the type of x2, τ₃ is the type of x3 and τ' is the type of e. That's the definition of a product type: it's the type of a tuple of elements of these types.

Here f has a type of the form 'a -> 'b, g has a type of the form 'b -> 'c and x has a type of the form 'a. It's apparent that f and g have function types since they're applied to an argument. Furthermore, since f is applied to x, the argument type of f is the same type as the type of x: both are 'a. Likewise, the return type of f and the argument type of g are the same type ('b) since g is applied to the value returned by f.

I don't know what you mean by “represents”. 'c stands for the type of x (which is alos the type of the argument of g). (This can be any type: the function is polymorphic.) 'b stands for the type of the argument of g (which is also the type of the return value of f). 'a stands for the type of the argument of f.

Upvotes: 1

Related Questions