// Reduce / Aggregate / Fold 
// Usual way makes deep recursion and trusts tail-opt: 
// (a,b,c,d,e,f,g,h) => (((((((a + b) + c) + d) + e) + f) + g) + h)
// This more is quicksort-style parallel: 
// (a,b,c,d,e,f,g,h) => (((a + b) + (c + d)) + ((e + f) + (g + h)))

// No Haskell Kinds support for F# so List and Array are easiest to make as separate methods.
open System.Threading.Tasks
module List = 
  let reduceParallel<'a> f (ie :'a list) =
    let rec reduceRec f (ie :'a list) = function
      | 1 -> ie.[0]
      | 2 -> f ie.[0] ie.[1]
      | len -> 
        let h = len / 2
        let o1 = Task.Run(fun _ -> reduceRec f (ie |> List.take h) h)
        let o2 = Task.Run(fun _ -> reduceRec f (ie |> List.skip h) (len-h))
        Task.WaitAll(o1, o2)
        f o1.Result o2.Result
    match ie.Length with
    | 0 -> failwith "Sequence contains no elements"
    | c -> reduceRec f ie c

module Array = 
  let reduceParallel<'a> f (ie :'a array) =
    let rec reduceRec f (ie :'a array) = function
      | 1 -> ie.[0]
      | 2 -> f ie.[0] ie.[1]
      | len -> 
        let h = len / 2
        let o1 = Task.Run(fun _ -> reduceRec f (ie |> Array.take h) h)
        let o2 = Task.Run(fun _ -> reduceRec f (ie |> Array.skip h) (len-h))
        Task.WaitAll(o1, o2)
        f o1.Result o2.Result
    match ie.Length with
    | 0 -> failwith "Sequence contains no elements"
    | c -> reduceRec f ie c

(*
Show case in F#-interactive with #time

> [1 .. 500] |> List.fold(fun a -> fun x -> System.Threading.Thread.Sleep(30);x+a) 0;;
Real: 00:00:15.654, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 125250
> [1 .. 500] |> List.reduceParallel(fun a -> fun x -> System.Threading.Thread.Sleep(30);x+a);;
Real: 00:00:02.710, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 125250
> [|1 .. 500|] |> Array.fold(fun a -> fun x -> System.Threading.Thread.Sleep(30);x+a) 0;;
Real: 00:00:15.639, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 125250
> [|1 .. 500|] |> Array.reduceParallel(fun a -> fun x -> System.Threading.Thread.Sleep(30);x+a);;
Real: 00:00:02.537, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 125250
*)