How do I avoid the Value Restriction error when the argument is an empty list?

Question

Some functions in the List module fail when the argument is an empty list. List.rev is an example. The problem is the dreaded Value Restriction.

I met the same problem while trying to define a function that returns a list with all but the last element of a list:

let takeAllButLast (xs: 'a list) =
    xs |> List.take (xs.Length - 1)

The function works well with nonempty lists, but a version that would handle empty lists fails:

let takeAllButLast (xs: 'a list) =
    if List.isEmpty xs then []
    else xs |> List.take (xs.Length - 1)
takeAllButLast []
error FS0030: Value restriction. The value 'it' has been inferred to have generic type
    val it : '_a list, etc.

I tried several things: making it an inline function, not specifying a type for the argument, specifying a type for the returned value, making the function depend on a type argument, and using the Option type to obtain an intermediate result later converted to list<'a>. Nothing worked.

For example, this function has the same problem:

let takeAllButLast<'a> (xs: 'a list) =
    let empty : 'a list = [] 
    if List.isEmpty xs then empty
    else xs |> List.take (xs.Length - 1)

A similar question was asked before in SO: F# value restriction in empty list but the only answer also fails when the argument is an empty list.

Is there a way to write a function that handles both empty and nonempty lists?

Note: The question is not specific to a function that returns all but the last element of a list.

Answer 1

The function itself is completely fine. The function does not "fail".
You do not need to modify the body of the function. It is correct.

The problem is only with the way you're trying to call the function: takeAllButLast []. Here, the compiler doesn't know what type the result should have. Should it be string list? Or should it be int list? Maybe bool list? No way for the compiler to know. So it complains.

In order to compile such call, you need to help the compiler out: just tell it what type you expect to get. This can be done either from context:

// The compiler gleans the result type from the type of receiving variable `l`
let l: int list = takeAllButLast []

// Here, the compiler gleans the type from what function `f` expects:
let f (l: int list) = printfn "The list: %A" l
f (takeAllButLast [])

Or you can declare the type of the call expression directly:

(takeAllButLast [] : int list)

Or you can declare the type of the function, and then call it:

(takeAllButLast : int list -> int list) []

You can also do this in two steps:

let takeAllButLast_Int : int list -> int list = takeAllButLast
takeAllButLast_Int []

In every case the principle is the same: the compiler needs to know from somewhere what type you expect here.

Alternatively, you can give it a name and make that name generic:

let x<'a> = takeAllButLast [] : 'a list

Such value can be accessed as if it was a regular value, but behind the scenes it is compiled as a parameterless generic function, which means that every access to it will result in execution of its body. This is how List.empty and similar "generic values" are implemented in the standard library.

But of course, if you try to evaluate such value in F# interactive, you'll face the very same gotcha again - the type must be known - and you'll have to work around it anyway:

> x   // value restriction
> (x : int list)  // works