F# Type 'int list' does not match the type 'int'

Question

I'm trying to construct a list which contains numbers of the Fibonacci sequence, but when I try to call the function later on it tells me that int list doesn't match int,

let rec fibonacci x list =
    if List.head list > x then List.tail list
    else fibonacci x (List.append (List.head list + (List.head (List.tail list))) list)


let x = 10
let list = [1;2]
let fibonacciList = fibonacci x list
printf "%A" fibonacciList

It says the editor is in the function call in the 2nd last line.
I'm new to F# and I'm sure it's a basic definitions error but I can't figure out what it is

TheQuickBrownFox TheQuickBrownFox · Accepted Answer · 2018-08-12T15:55:57

When you remove the call to the fibonacci function the compiler actually reveals the true error: error FS0071: Type constraint mismatch when applying the default type ''a list' for a type inference variable. The types ''a' and ''a list' cannot be unified. Consider adding further type constraints

This is hard to understand but basically there is something wrong with the implementation. I think the problem is your use of List.append. It should take two lists but you provide it with an int and an int list. You can add one item to the front of a list with the :: operator:

let rec fibonacci x list =
    if List.head list > x then List.tail list
    else fibonacci x ((List.head list + (List.head (List.tail list))) :: list)

Here is an equivalent implementation that uses pattern matching to simplify the code:

let rec fibonacci x list =
    match list with
    | a :: b :: rest ->
        if a > x then b :: rest
        else fibonacci x (a + b :: list)

Note that the compiler warns that the match cases are incomplete. This function will throw an exception if the list has less than 2 items.

Also note that this doesn't work properly: it doesn't produce the Fibonacci sequence. I will leave it with you to fix that.

F# Type 'int list' does not match the type 'int'

1 Answers