CODEWITHSUNDEEP
f#
name
name

Reputation: 419

Understanding type mismatch error?

Why does this statement give me a type mismatch error, 

let x = List.rev [] in (3::x, true::x);;

while this statement does not? 

let x = [] in (3::x, true::x);;

I'm assuming it is because x is given a function call in the first statement, while it is only give an empty list in the second statement. But, I am not sure exactly why the second works and the first does not? Any help will be much appreciated. Thanks!

Upvotes: 2

Views: 85

Answers (1)

rmunn
rmunn

Reputation: 36688

Try the following:

let x = [] ;;

Result: val x : 'a list. F# knows that x is a list of as-yet unknown type. If it had any contents, its type would be known. This works perfectly well.

But the following will not work:

let x = List.rev [] ;;

Result:

error FS0030: Value restriction. The value 'x' has been inferred to have generic type

val x : '_a list

Either define 'x' 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.

The "value restriction" error in F# can be hard to understand — why is [] allowed when List.rev [] is not? — but this article goes into some details. Essentially, F# can always feel safe making functions generic, but it can only feel safe making values generic if the following two conditions apply:

  1. The expression on the right-hand side of the let is a pure value, e.g. it has no side-effects, and
  2. The expression on the right-hand side of the let is immutable.

When the expression is [], then F# knows that it's a pure, immutable value, so it can make it generic ('a list). But when the expression is someFunction [], the F# compiler doesn't know what someFunction is going to do. Even though in this case, we know that List.rev is part of the standard library and matches those two scenarios, the F# compiler can't know that. In a completely pure language like Haskell, you can know from a function's type signature that it's pure, but F# is a more pragmatic language. So F# takes the guaranteed-safe approach and does not make the result of List.rev [] generic.

Therefore, when you write let x = [] in (3::x, true::x), the [] value is a generic empty list, so it can become either an int list or a bool list as needed. But when you write let x = List.rev [] in (3::x, true::x), F# cannot make List.rev [] generic. It can say "This is a list of a type I don't yet know", and wait for the type to become clear. Then the first expression of a specific type that uses this list, in this case 3::x, will "lock" the type of that list. I.e., F# cannot consider this list to be generic, so now it has figured out that this empty list is an empty list of ints. And then when you try to append a bool to an empty int list, that's an error.

If you flipped the tuple around so that it was true::x, 3::x then the type error would "flip" as well: it would expect a bool list and find an int list.

So the short version of this answer is: you're hitting the F# value restriction, even though that's not immediately obvious since the error you got didn't mention value restriction at all.

See Understanding F# Value Restriction Errors for a good discussion of the value restriction, including the most common place where you'd normally see it (partially-applied functions).

Upvotes: 3

Related Questions