2 people like it.
Like the snippet!
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.
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

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
More information