sicmutils.algebra.fold — sicmutils 0.21.1

Namespace implementing various aggregation functions using the fold abstraction and combinators for generating new folds from fold primitives.

Contains a number of algorithms for compensated summation of floating-point numbers.

constant clj/s

(constant const)

Given some value const, returns a fold that ignores all input and returns const for a call to any of its arities.

count clj/s

(count)

(count pred)

Given some predicate pred, returns a fold that counts the number of items it encounters that return true when passed to pred, false otherwise.

fold->scan-fn clj/s

(fold->scan-fn fold)

(fold->scan-fn fold present)

(fold->scan-fn init fold present)

Given

• a 0-argument fn init that returns some "empty" accumulating value

• a 2-argument fn fold of (accumulator, x) => accumulator responsible for merging some value x into the ongoing accumulation

• a 1-argument fn present from accumulator => final-result

Returns a function with two arities. The first arity takes a sequence xs and returns a lazy sequence of all intermediate results of the summation. For example, given [0 1 2 3], the return sequence would be equivalent to:

(def sum-fn (fold->sum-fn init fold present))

[(sum-fn [0])
 (sum-fn [0 1])
 (sum-fn [0 1 2])
 (sum-fn [0 1 2 3])]

The second arity takes a transformation function f, an inclusive lower bound low and an exclusive upper bound high and returns a lazy sequence of all intermediate results of accumulating (map f (range low high)).

Other Arities

Given a single argument fold, fold is passed as each of the 0, 1 and 2 arity arguments.

Given fold and present, fold is used for the 0 and 2 arity arguments, present for the 1-arity argument.

fold->sum-fn clj/s

(fold->sum-fn fold)

(fold->sum-fn fold present)

(fold->sum-fn init fold present)

Given

• a 0-argument fn init that returns some "empty" accumulating value

• a 2-argument fn fold of (accumulator, x) => accumulator responsible for merging some value x into the ongoing accumulation

• a 1-argument fn present from accumulator => final-result

Returns a function with two arities. The first arity takes a sequence xs and returns the result of accumulating all elements in xs using the functions above, then presenting the result.

The second arity takes a transformation function f, an inclusive lower bound low and an exclusive upper bound high and returns the result of accumulating (map f (range low high)).

Other Arities

Given a single argument fold, fold is passed as each of the 0, 1 and 2 arity arguments.

Given fold and present, fold is used for the 0 and 2 arity arguments, present for the 1-arity argument.

generic-sum-fold clj/s

(generic-sum-fold)

(generic-sum-fold acc)

(generic-sum-fold acc x)

Fold-style function. The 2-arity merge operation adds the value x into the accumulating stating using sicmutils.generic/+.

• given 0 arguments, returns an accumulator of 0.0
• given a single argument acc, acts as identity.

join clj/s

(join)

(join fold)

(join fold & folds)

Given some number of folds, returns a new fold with the following properties:

• the accumulator is a vector of the accumulators of each input fold
• each x is merged into each accumulator using the appropriate fold
• present is called for every entry in the final vector

Given a single fold, acts as identity.

The no-argument call (join) is equivalent to ([[constant]] []).

kahan clj/s

(kahan)

(kahan [acc _])

(kahan [acc c] x)

Fold that tracks the summation of a sequence of floating point numbers, using the Kahan summation algorithm for maintaining stability in the face of accumulating floating point errors.

kahan-babushka-klein clj/s

(kahan-babushka-klein)

(kahan-babushka-klein acc)

(kahan-babushka-klein [acc cs ccs] x)

Implements a fold that tracks the summation of a sequence of floating point numbers, using a second-order variation of kahan-babushka-neumaier.

See this Wikipedia page for more information.

This algorithm was proposed by Klein in 'A Generalized Kahan-Babushka Summation Algorithm', along with the higher-order versions implemented by kbk-n.

kahan-babushka-neumaier clj/s

(kahan-babushka-neumaier)

(kahan-babushka-neumaier acc)

(kahan-babushka-neumaier [acc c] x)

Implements a fold that tracks the summation of a sequence of floating point numbers, using Neumaier's improvement to kahan.

This algorithm is more efficient than kahan, handles a wider range of cases (adding in numbers larger than the current running sum, for example) and should be preferred.

kbk-n clj/s macro

(kbk-n n)

Given some order n, returns a fold implementing n-th order Kahan-Babushka-Klein summation.

Given n == 0, this is identical to a naive sum. Given n == 1, identical to kahan-babushka-neumaier. Given n == 2, identical to kahan-babushka-klein.

n > 2 represent new compensated summation algorithms.

kbn clj/s

Alias for kahan-babushka-neumaier.

max clj/s

(max)

(max acc)

(max acc x)

Fold that stores its maximum encountered value in its accumulator, and returns it when called on to present.

Accumulation initializes with nil.

min clj/s

(min)

(min acc)

(min acc x)

Fold that stores its minimum encountered value in its accumulator, and returns it when called on to present.

Accumulation initializes with nil.