F# value restriction

Question

I have read all treads about value restriction in F#, but I still not understand it. I have the following code:

type tree<'a> = 
    | Nil
    | Node of (tree<'a> * 'a * tree<'a>)

let rec flatten = function
    | Nil -> []
    | Node ( Nil, b, Nil ) -> [b]
    | Node ( l, h, p ) -> List.concat [(flatten l);[h];(flatten p)]

and the compiler show an error:

error FS0030: Value restriction. The value 'it' has been inferred to have generic type
    val it : '_a list    
Either define 'it' 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.

Can anyone help me? Thank you very much;)

Subdivision

Can you provide code calling flatten? I can compile and run this sample just fine – Chowder

but when I calling flatten Nill;; there is a problem. – Subdivision

Answer 1

Allow me to use my psychic debugging skills. You cannot call flatten Nil because, as the compiler indicates, the result could be an 'a list for any type 'a. You must add a type annotation, such as (flatten Nil : int list).

On an unrelated note, your second case in the definition of flatten is unnecessary and can be removed since it's also covered by the third case.

Quinta

As for the unrelated note of "second case in the definition of flatten is unnecessary and can be removed since it's also covered by the third case", could the performance be better with the second case since it will reduce a lot of extra matches? – Marthamarthe

@dc7a9163d9 - yes, that's certainly possible. But I'd default to the simplest thing and only introduce such optimizations if performance isn't meeting goals. – Quinta