CODEWITHSUNDEEP
f#
Khaine775
Khaine775

Reputation: 2765

F# Matching results of recursive calls using higher order functions

Given a simple function, where we do pattern matching on the result of a recursive call, such as:

let rec sumProd = function
    | []      -> (0,1)
    | x::rest -> let (rSum,rProd) = sumProd rest
                 (x + rSum,x * rProd)

sumProd [2;5] //Expected (7, 10)

How would I go about changing it into something using higher order functions, e.g. foldBack?

let sumProdHigherOrder lst = 
    List.foldBack (fun x acc -> (acc + x, acc * x)) lst (0,0)

The above seemed almost like the way to do it, but calling it gives the error: The type 'int' does not match the type 'int * int'

sumProdHigherOrder [2;5] //Expected (7, 10)

What am I missing?

Upvotes: 2

Views: 156

Answers (2)

Gus
Gus

Reputation: 26184

Your missing the tuple functions fst and snd:

List.foldBack (fun x acc -> (fst acc + x, snd acc * x)) [2;5] (0,1)
// val it : int * int = (7, 10)

Or even better, decomposing the tuple at the lambda. I see you just found it:

List.foldBack (fun x (s, m) -> (s + x, m * x)) [2;5] (0,1)

Also note that since the operations are commutative you can do a straight fold:

List.fold (fun (s, m) x -> (s + x, m * x)) (0,1) [2;5]

It will be more efficient.

Upvotes: 5

Khaine775
Khaine775

Reputation: 2765

Right! Of course it shouldn't be the same accumulator that gets passed through the list. After staring intensely at the code for some minutes, I figured it out:

let sumProdHigherOrder lst = 
    List.foldBack (fun x (acc,acc') -> (acc + x, acc' * x)) lst (0,1)

Upvotes: 2

Related Questions