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;)

Can you provide code calling flatten? I can compile and run this sample just fine — JaredPar, Nov 01 '10 at 19:10

score 11 · Accepted Answer · answered Nov 01 '10 at 19:21

11

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.

answered Nov 01 '10 at 19:21

kvb

54,864
2
91
133

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? – ca9163d9 Jun 22 '15 at 03:19
@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. – kvb Jun 22 '15 at 15:54

F# value restriction

1 Answers1