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 ()?

Alberto Solano · Accepted Answer · 2016-04-02 16:46:36Z

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.

Fyodor Soikin · Accepted Answer · 2016-04-02 16:08:40Z

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.

answered Apr 2, 2016 at 16:08

Fyodor Soikin

81.3k10 gold badges134 silver badges179 bronze badges

3 Comments

Bad Over a year ago

And you didn't actually need to annotate f with a type. That was an extraneous step. But without this extraneous step (if all else is correct), it still throws an error: Value restriction. The value 'f' has been inferred to have generic type val f : '_a >Either define 'f' as a simple data term, make it a function with explicit arguments or, if you do not intend for it to be generic, add a type annotation.

Fyodor Soikin Over a year ago

You're right, I forgot about value restriction. But if you make f a function, then that problem will disappear anyway.

Bad Over a year ago

If you make f() and then call it (all else being correct), it still throws this Value restriction exception. So it seems the only way out is to state unit explicitly. But still thanks for answers, they are all really helpful.

Collectives™ on Stack Overflow

Recursive function parameters

2 Answers 2

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related