F# - Error when composing a function with itself

Question

In F# I can define an add1 function

let add1 x = x + 1

I can then define an add2 as the add1 function called on itself

let add2 x = add1 (add1 x)

Or by composing the add1 function with itself

let add2 = add1 >> add1

I was trying to implement the lambda calculus combinators in F#, the first being Identity

let I x = x

I then tried to define the Identity of Identity

let II = I >> I

But this caused the following compilation error:

Value restriction. The value 'II' has been inferred to have generic type val II : ('_a -> '_a) Either make the arguments to 'II' explicit or, if you do not intend for it to be generic, add a type annotation

I can however define it as

let II x = I (I x)

I'm new to F# and am curious why?

Answer 1

This error has nothing to do with function composition itself, it's about Value Restriction. It happens because F# compiler infers types as generic as possible, but although it can easily generalize function, it can't generalize value (even though your value is in fact a function).

This answer can help you avoid this problems, but basically you should specify an input parameter:

let II x = (I>>I) x

or

let II x = I >> I <| x

Answer 2

@kagetogi is right.

The F# compiler wants to resolve values into concrete types and it will try to do so as soon as you use the function the first time. So this fails:

let I  x = x
let II   = I >> I

But this works:

let I  x = x
let II   = I >> I

II 5   |> printfn "%A" 

Here II has type int->int. Which means that the following fails:

let I  x = x
let II   = I >> I

II 5   |> printfn "%A" 
II 5.0 |> printfn "%A" 

Because the second call is expecting an int not a float.

That is why in F# the pipe |> operator is preferred over the composition operator >>.

let I   x = x
let II  x = x |>  I |> I
let II' x = x |> (I >> I)

Now finally II has generic type 'a->'a. They both achieve function composition in the end.

Adding the code annotation also works:

let II<'a> : 'a->'a = I >> I