sicmutils.util.aggregate — sicmutils 0.21.1

Namespace with algorithms for aggregating sequences in various ways.

*cutoff* clj/s

Dynamically bindable size below which pairwise-sum will defer to sum to aggregate values.

*fold* clj/s

Fold used to aggregate values encountered by sum or [[fold]].

Rebind this value to change the behavior of sum or [[fold]].

Defaults to [[sicmutils.algebra.fold/kahan-babushka-neumaier-fold]].

generic-sum clj/s

(generic-sum xs)

(generic-sum f low high)

Sums either:

• a series xs of numbers, or
• the result of mapping function f to (range low high)

Using the generic sicmutils.generic/+ function.

group clj/s

(group minus plus invert id)

(group minus plus invert id annihilate?)

Similar to monoid for types with invertible elements. Accepts:

• binary minus and (associative) plus functions
• a unary negate function
• an element id that obeys (plus id other) == (plus other id) == other
• optionally, an annihilate? function that should return true for any x such that (plus x <any>) == x.

And returns a function that will SUBTRACT elements. Given x, y, z, for example, the returned function will return (- x y z), implemented as (minus x (plus y z))

If the annihilate? function is supplied, then if the aggregation produces a value that returns (annihilate? true) at any point, the reduction will return immediately.

merge-fn clj/s

(merge-fn compare add zero? make)

NOTE that the returned function recurs on increasing indices internally instead of walking through the lists directly. This method of traversing vectors is more efficient, and this function is called so often that the performance gain is worth it, and reads almost like the explicit sequence traversal.

monoid clj/s

(monoid plus id)

(monoid plus id annihilate?)

Accepts a binary (associative) aggregation function plus and an identity element id and returns a multi-arity function that will combine its arguments via plus. A 0-arity call returns id.

optionally takes an annihilate? function that should return true for any x such that (plus x <any>) == x.

If the annihilate? function is supplied, then if the aggregation produces a value that returns (annihilate? true) at any point, the reduction will return immediately.

pairwise-sum clj/s

(pairwise-sum xs)

(pairwise-sum f low high)

Given a vector of numbers, returns the pairwise summation of the vector generated by arranging the vector into a binary tree and summing leaves together all the way up to the root.

If xs is /not/ a vector, pairwise-sum will realize all elements into a vector before operating.

If the initial vector, or some recursive slice, reaches a count <= *cutoff*, pairwise-sum defers to (reduce + xs).

Performance Discussion

pairwise-sum is perhaps 10% faster than sum with sicmutils.algebra.fold/kbn bound to *fold*, but has poorer bounds on its error growth. Instead of having roughly constant error regardless of the size of the input, in the worst case its accumulated error grows with $O(\log n)$.

This improvement is due to the fact that pairwise-sum tends to add up numbers of similar magnitude, instead of adding deltas into a progressively larger sum.

This implementation was inspired by the pairwiseSum implementation in the math-functions Haskell package. The notes above were adapted from that function's docs.

scan clj/s

(scan xs)

(scan f low high)

Takes either:

• a series xs of numbers
• A transformation function f, an inclusive-lower bound low and exclusive-upper bound upper

And returns a lazy sequence of all intermediate values seen while aggregating either xs or (map f (range low high)) using the fold dynamically bound to *fold*.

Use binding to substitute in a different fold:

(require '[sicmutils.algebra.fold :as af])

(binding [*fold* (af/join af/kahan af/min af/max)]
  (scan inc 0 3))
;;=> ([1.0 1 1] [3.0 1 2] [6.0 1 3])

sum clj/s

(sum xs)

(sum f low high)

Takes either:

• a series xs of numbers
• A transformation function f, an inclusive-lower bound low and exclusive-upper bound upper

And returns the result of aggregating either xs or (map f (range low high)) using the fold dynamically bound to *fold*.

Use binding to substitute in a different fold:

(require '[sicmutils.algebra.fold :as af])

(binding [*fold* (af/join af/kahan af/min af/max)]
  (sum inc 0 10))
;;=> [55.0 1 10]