 2 people like it.

# Seq.reduceBallanced function

The function has the same type as Seq.reduce. Instead of reducing elements from the left to the right, it splits the input into two halves, reduces each half separately and then aggregates the results using the given function. This means that the values are aggregated into a ballanced tree, which can save stack space.

## Implementation

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: ``` ``````module Seq = /// Reduces input sequence by splitting it into two halves, /// reducing each half separately and then aggregating the results /// using the given function. This means that the values are /// aggregated into a ballanced tree, which can save stack space. let reduceBallanced f input = // Convert the input to an array (must be finite) let arr = input |> Array.ofSeq let rec reduce s t = if s + 1 >= t then arr.[s] else // Aggregate two halves of the input separately let m = (s + t) / 2 f (reduce s m) (reduce m t) reduce 0 arr.Length ``````

## Example using binary trees

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: ``` ``````/// Simple tree type with data in leaves type Tree = | Node of Tree * Tree | Leaf of int /// Returns the size of a tree member x.Size = match x with | Leaf _ -> 1 | Node(t1, t2) -> 1 + (max t1.Size t2.Size) // Aggregate 1000 leaves in a tree let inputs = [ for n in 0 .. 1000 -> Leaf n] // 'reduceBallanced' creates tree with size 11 let t1 = inputs |> Seq.reduceBallanced (fun a b -> Node(a, b)) t1.Size // Ordinary 'reduce' creates tree with size 1001 let t2 = inputs |> Seq.reduce (fun a b -> Node(a, b)) t2.Size ``````
module Seq

from Microsoft.FSharp.Collections
val reduceBallanced : f:('a -> 'a -> 'a) -> input:seq<'a> -> 'a

Full name: Script.Seq.reduceBallanced

Reduces input sequence by splitting it into two halves,
reducing each half separately and then aggregating the results
using the given function. This means that the values are
aggregated into a ballanced tree, which can save stack space.
val f : ('a -> 'a -> 'a)
val input : seq<'a>
val arr : 'a []
module Array

from Microsoft.FSharp.Collections
val ofSeq : source:seq<'T> -> 'T []

Full name: Microsoft.FSharp.Collections.Array.ofSeq
val reduce : (int -> int -> 'a)
val s : int
val t : int
val m : int
property System.Array.Length: int
type Tree =
| Node of Tree * Tree
| Leaf of int
member Size : int

Full name: Script.Tree

Simple tree type with data in leaves
union case Tree.Node: Tree * Tree -> Tree
union case Tree.Leaf: int -> Tree
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
val x : Tree
member Tree.Size : int

Full name: Script.Tree.Size

Returns the size of a tree
val t1 : Tree
val t2 : Tree
val max : e1:'T -> e2:'T -> 'T (requires comparison)

Full name: Microsoft.FSharp.Core.Operators.max
property Tree.Size: int

Returns the size of a tree
val inputs : Tree list

Full name: Script.inputs
val n : int
val t1 : Tree

Full name: Script.t1
Multiple items
module Seq

from Script

--------------------
module Seq

from Microsoft.FSharp.Collections
val a : Tree
val b : Tree
val t2 : Tree

Full name: Script.t2
val reduce : reduction:('T -> 'T -> 'T) -> source:seq<'T> -> 'T

Full name: Microsoft.FSharp.Collections.Seq.reduce