What is wrong with this F# curried function?

Question

I'm writing this curried f# function called inner that should take 2 lists as parameters and multiply both according to position and then return the sum:

let rec inner xs = 
    let aux ys = function
    | ([], ys) -> 0
    | (xs, []) -> 0
    | (x::xs, y::ys) -> (x*y) + inner xs ys
    aux ys;;
inner [1;2;3] [4;5;6];;

In this case the answer is 32 because 1*4 + 2*5 + 3*6 = 32. And it works but there's this message:

error FS0001: Type mismatch. Expecting a
'a list -> 'd
but given a
'b list * 'a list -> int

The type 'a list does not match the type 'b list * 'a list

I honestly don't know what to put next to aux when calling it to make it work.

Answer 1

You need to call your aux function after defining it. Currently your inner function just defines it by doesn't do anything with it.

In this case, I'm not sure you actually need to define aux at all, if you define your inner function to take two parameters:

let rec inner (tuple : int list * int list) =
    match tuple with
    | ([], ys) -> 0
    | (xs, []) -> 0
    | (x :: xtail, y :: ytail) -> x * y + inner (xtail, ytail)

inner ([1;2;3], [4;5;6]) // 32

If you want to retain the curried form then the following should work. You need to include xs in the matching, and then just return aux (which will incorporate the first list and expect a second list):

let rec inner xs = 
    let aux ys =
        match xs, ys with
        | ([], ys) -> 0
        | (xs, []) -> 0
        | (x::xs, y::ys) -> (x*y) + inner xs ys
    aux

inner [1;2;3] [4;5;6];; // 32

Answer 2

I'm not sure what exactly the misunderstanding is. I'm noticing three strange points:

• let aux ys = function ([], ys) -> declares and immediately re-declares, and thereby shadows, the identifier ys. Note that aux is a function with two curried arguments, of which the second is a 2-tuple. I doubt this is what you intended.

• The aux function is indented in a rather unusual way; normally, it should get another four-space indentation. The compiler may not complain about this, and just exit the scope after the pattern match, but it adds to the confusion about what the failing line is supposed to do.

• ys is undefined where it is last used. (Could this be related to the confusing indentation?)

Here are two ways to write it:

Not tail recursive

let rec inner xs ys = 
    match xs, ys with
    | x::xt, y::yt -> x * y + inner xt yt
    | _ -> 0

In this version, the curried arguments are turned into a tuple and used in a match expression. (Due to the final additions, this may cause a stack overflow for large input lists.)

Tail recursive, with auxiliary function

let rec private aux acc = function
    | x::xs, y::ys -> aux (acc + x * y) (xs, ys)
    | _ -> acc

let inner xs ys = aux 0 (xs, ys)

Here, the auxiliary function has two curried arguments, of which the first is an accumulator, and the second a tuple holding the two lists. inner becomes a wrapper function that both strips the accumulator – by initializing it with zero – and turns the tupled arguments into curried arguments, as was the requirement. (Since the recursive call's value is the functions return value, tail recursive compilation is supported for this function.)