F# function - expected type differs from actual

Question

I have been trying to write a curried function "multvec" which uses u=(u1, u2, ..., un) and v=(v1, v2, ..., vn) and outputs u1*v1 + u2*v2 + ... + un*vn. I think I have the logic mostly correct (at least it would be in other languages...) but I keep getting an:

stdin(11,57): error FS0001: This expression was expected to have type
'a list    
but here has type
'c list * 'd list -> 'b list

The code is below: The problem is clearly in the call to product in the last line. However, I was under the impression that the base case ( x * y )::[ ] would just product an 'a list, instead of what it actually produces.

let rec multvec xs ys = function
    | [ ], [ ] -> failwith "Both lists cannot be empty"
    | x::[ ], y::[ ] -> ( x * y )::[ ]
    | x::xs, y::ys -> let product = multvec xs ys
                      ( x * y ) + ( List.reduce (+) product )

Any clarity on this error would be greatly appreciated! Thank you in advance.

Answer 1

Your code honestly has more wrong with it than right: ;-]

• It's not tail-recursive
• Use of function when xs and ys are separate parameters
• Incomplete pattern match
• Having one branch evaluate to a list and another evaluate to a scalar
• All products are manually added together except for the last, which has a List.reduce run over a single-element list – slightly backwards ;-]

Here's a sensible implementation that fixes all of the above:

let inline multvec xs ys = List.map2 (*) xs ys |> List.sum

Note that if performance is a primary concern then it may be worth avoiding List.sum, as it uses checked arithmetic. One could do the following instead if using unchecked arithmetic is okay:

let inline multvec xs ys = List.map2 (*) xs ys |> List.reduce (+)

If you really want to do this manually, here's one approach:

let inline multvec xs ys =
    let rec impl acc = function
        | [], []         -> acc
        | x::xs', y::ys' -> impl (x * y + acc) (xs', ys')
        | _              -> failwith "lists must be of equal length" 
    impl LanguagePrimitives.GenericZero (xs, ys)

Answer 2

To add to ildjarn's answer, you can fuse map2 and reduce into a single function call using fold2 to compute the dot product ("multvec") of two vectors:

let inline dot xs ys =
    let zero = LanguagePrimitives.GenericZero
    List.fold2 (fun acc x y -> acc + x * y) zero xs ys

This would save you from creating an unnecessary temporary list.