Recursion in F#, expected type int but got type “int list -> int”

Question

I'm new to F# and want to implement a least common multiple function of a list by doing it recursively, e.g. lcm(a,b,c) = lcm(a, lcm(b,c)), where lcm of two elements is calculated from the gcd.

I have the following code. I try to match the input of the lcm function with a list of two elements, and otherwise a general list, which I split up into its first element and the remaining part. The part "lcm (tail)" gives a compiler error. It says it was expected to have type "int" but has type "int list -> int". It looks like it says that the expression "lcm tail" is itself a function, which I don't understand. Why is it not an int?

let rec gcd a b =
    if b = 0
        then abs a
    else gcd b (a % b)

let lcmSimple a b = a*b/(gcd a b)

let rec lcm list = function
    | [a;b] -> lcmSimple a b
    | head::tail -> lcmSimple (head) (lcm (tail))

Best regards.

but still take a notice to warning - you don't process all from possible cases. — FoggyFinder
@FoggyFinder you are right, it works if I remove "list", but usually you include an argument to your function. I realize I never use "list", and maybe it's a matching thing. Also, I have included the empty case. — HowDoICSharply
let rec lcm list = function | ... is shorthand for let rec lcm list x = match x with | ... so your function takes 2 arguments, not 1. — Lee
So, someone have to write answer. @HowDoICSharply do you want to do it? — FoggyFinder

HowDoICSharply HowDoICSharply · Accepted Answer · 2017-10-24T16:33:13

When defining the function as let f = function | ..., the argument to the function is implicit, as it is interpreted as let f x = match x with | ....

Thus let rec lcm list = function |... is a function of two variables, which are list and the implicit variable. This is why the compiler claims that lcm tail is a function - only one variable has been passed, where it expected two. A better version of the code is

let rec gcd a b =
    if b = 0
        then abs a
    else gcd b (a % b)

let lcmSimple a b = a*b/(gcd a b)

let rec lcm = function
    | [a;b] -> lcmSimple a b
    | head::tail -> lcmSimple (head) (lcm (tail))
    | [] -> 1

where the last case has been included to complete the pattern.

Recursion in F#, expected type int but got type “int list -> int”

1 Answers