Recursive function parameters

Question

I made a simple recursive function, and expected it to work (but it doesn't):

open System
open System.Threading

let f =
    let r = Random()
    let rec d =
        printfn "%d" (r.Next())
        Thread.Sleep(1000)
        d
    d
f

With the help of Intellisense I ended up with the following working function (but without understanding why previous function didn't work):

open System
open System.Threading

let f : unit =
    let r = Random()
    let rec d() =
        printfn "%d" (r.Next())
        Thread.Sleep(1000)
        d()
    d()
f

So why do I need to explicitly state unit and ()?

Answer 1

In the first version, you declared a recursive object (let rec d), or a value. You're saying that the d object is recursive, but how an object could be recursive? How does it call itself? Of course, this doesn't make sense.

It's not possible to use recursive objects in F# and this is the reason why your first version doesn't work.

In the second version, you declared a recursive function (let rec d()). Adding (), you're explicitly stating that d is a function. Furthermore you explicitly stated, with unit, that the function f (called just once) will not return anything, or, at least, you're saying that f will return a value of a not specific type. In F#, even the simplest functions must always return a value.

In your case, F# will try to infer the type that f will return. Because there's no specific type annotation and your f is not doing something (like a calculation) that will return a specific value using a specific type, the F# compiler will assign a generic return type to f, but your code is still ambiguous and you have to specify the unit type (the simplest type that a F# function could return) to be more specific.

The value restriction error is related indeed to F#'s powerful type inference. Please have a look at this interesting article about this error.

Answer 2

In your first attempt, you define not a function, but a value. The value d is defined in terms of itself - that is, in order to know what d is, you need to first know what d is. No wonder it doesn't work!

To make this a bit more clear, I will point out that your definition is of the same kind as this:

let x = x

Would you expect this to work?

In your second attempt, you gave d a parameter. It is the parameter that made it a function and not a value. Compare:

let rec x() = x()

This will still cause a stack overflow when executed, but at least it will compile: it's a function that unconditionally calls itself.

You didn't have to give it specifically a unit parameter, any parameter would do. You could have made it a number, a string, or even a generic type. It's just that unit is the simplest option when you don't care what it is.

And you didn't actually need to annotate f with a type. That was an extraneous step.

In conclusion, I'd like to point out that even in your second code block, f is still a value, not a function. In practical terms it means that the code inside f will be executed just once, when f is defined, and not every time you mention f as part of some other expression, which is apparently what you intuitively expect.