Type mismatch with Async in F#

Question

I've just started messing around with F# and am trying to do some basic parallel computation to get familiar with the language. I'm having trouble with type mismatches. Here's an example:

let allVariances list =
    seq {
        for combination in allCombinations list do
            yield (combination, abs(targetSum - List.sum combination))
    }

let compareVariance tup1 tup2 =
    if snd tup1 < snd tup2 then
        tup1
    else
        tup2

let aCompareVariance tup1 tup2 =
    async { return compareVariance tup1 tup2 }

let matchSum elements targetSum =
    allVariances elements
    |> Seq.reduce aCompareVariance
    |> Async.Parallel
    |> Async.RunSynchronously

So, "allVariances elements" produces a seq<float list * float>. CompareVariance takes two of those <float list * float> tuples and returns the one with the smaller second item (variance). My goal is to use Reduce to end up with the tuple with the smallest variance. However, I get a type mismatch on the aCompareVariance argument:

Error 1 Type mismatch. Expecting a float list * float -> float list * float -> float list * float but given a float list * float -> float list * float -> Async<float list * float> The type 'float list * float' does not match the type 'Async<float list * float>'

It seems like the Async return type isn't accepted by Reduce?

Answer 1

Seq.reduce takes a function and a sequence and reduces the list using the function. That is, the outcome of reducing a sequence {a1;a2;a3;...;an} with function f will be f(f(...f(f(a1,a2),a3),...),an))...). However, the function you're passing can't be applied this way, because the return type (Async<float list * float>) doesn't match the argument types (float list * float). What exactly are you trying to achieve?

Also, keep in mind that async computations are great for asynchronous work, but not ideal for parallel work. See F#: Asynch and Tasks and PLINQ, oh my! and Task Parallel Library vs Async Workflows.

EDIT

Here's one way to write a function which will reduce items more like you expected, operating sort of like this:

[|a1; a2; a3; a4|]
[|f a1 a2; f a3 a4|]
f (f a1 a2) (f a3 a4)

At each stage, all applications of f will take place in parallel. This uses Async.Parallel, which as mentioned above is probably less appropriate than using the Task Parallel Library (and may even be slower than just doing a normal synchronous Array.reduce). As such, just consider this to be demonstration code showing how to piece together the async functions.

let rec reduce f (arr:_[]) =
  match arr.Length with
  | 0 -> failwith "Can't reduce an empty array"
  | 1 -> arr.[0]
  | n ->
      // Create an array with n/2 tasks, each of which combines neighboring entries using f
      Array.init ((n+1)/2) 
        (fun i -> 
           async { 
             // if n is odd, leave last item alone
             if n = 2*i + 1 then
               return arr.[2*i]
             else
               return f arr.[2*i] arr.[2*i+1]}) 
      |> Async.Parallel |> Async.RunSynchronously
      |> reduce f

Note that converting items to and from Async values all happens internally to this function, so it has the same type as Array.reduce and would be used with your normal compareVariance function rather than with aCompareVariance.