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
Raw view New version

More information

Link:http://fssnip.net/72
Posted:6 years ago
Author:Tomas Petricek
Tags: sequence , tree , reduce , aggregate , stack