PackageDescription: Reducers


Reducers

Last published: May 31, 2017 by 'stm'

Defines 26 Classes
Extends 36 Classes

Reducers is a library and model for efficient collection processing. It emphasizes composition and lays a foundation for parallel collection processing. Support for custom collection-like types can be implemented easily.

Overview
## Source Collections
A source collection can be any object that understands #reduce:init: and #reduce: (also called a Reducible). The package provides the necessary extensions for collections, streams, random number generators and block closures generating sequences of elements. The abstract class #Reducible implements additional convenient methods. For example, #cat: concatenates two collections lazily, i.e., without building a new collection.

## Transformations
Transformations, e.g., mapping and filtering, are defined independently of the type of the source collections using transducers. Applying a transducer to a collection creates a virtual collection (also called Reducer) that provides a transformed view on the source.

## Result Aggregation
After applying transducers, the result can be either aggregated in a collection or computed by calling #reduce:init: / #reduce: on a (virtual) collection.

Usage
Reducers provides two API styles for transformations: compositional and classic. The compositional style uses #<~ to indicate the data flow from a source through various transformations into a drain. The classic style is similar to the ST collection API to facilitate easy code adaption. See the protocol provided by the package Reducers Classic API.

## Introductory Example
The example uses symbols instead of blocks for the sake of brevity.

| squares sum set |
"squared odd numbers, virtual collection"
squares := #squared mapping <~ #odd filtering <~ (1 to: 10).

"calculating the sum"
sum := (#+ initialValue: 0) <~ squares.

"aggregating the numbers in a set"
set := Set <~ squares.

Using the classical transformation API, the first statement can be written as:

| squares |
squares := ((1 to: 10) reducing filter: #odd) map: #squared.

## Result Aggregation
The principal method to aggregate results is #reduce:init: / #reduce:. The semantic is similar to #inject:into: but differs in two points:
* Invoked with a ternary block or symbol (called reducing function), it will evaluate it with the running value and the current key and value.
* If a ReducedNotification is raised, #reduce:init: stops and returns the current running value.

| sum dict |
sum := (1 to: 10) reduce: #+ init: 0.
dict := #(one two three)
reduce: [:dict :key :val | dict at: key put: val; yourself]
init: Dictionary new.

To aggregate results in a collection more easily, use #<~, which is understood by collections and collection classes as well.

| col dict |
dict := Dictionary with: 0 -> #zero.
dict <~ #(one two three).
col := OrderedCollection <~ (1 to: 10).
col <~ (11 to: 20).

A reduction is a reducing function and an initial value. It serves as a deferred computation that can be reused with different reducibles.

| sum first second |
sum := #+ initialValue: 0.
first :=(1 to: 10) reduce: sum.
second := sum <~ #(0.1 0.2 0.3).

Custom types should implement #<~ to support easy result adding, too.

## Transformations
Transducers provides many common collection transformations, e.g., filtering, mapping and flattening. For a complete list see the subclasses of Transducer.
To create a transducer, send a corresponding message to either a block, a symbol or number.

[:x | x < 0.01] filtering.
#squared mapping.
10 taking.

There are three exceptions, the singleton classes Catting, Flattening and Identity. In expressions with #<~, the classes can be used directly. To access their instances, send #transducer to the class.

Catting transducer.
Flattening transducer.
Identity transducer.

Transducers can be composed and applied to (virtual) collections and reductions.

| oneToTen oddSquares sum set |
"virtual collection"
oneToTen := Flattening <~ #(1 2 3 4 5 (6 7 8 (9 10))).

"composed transducer"
oddSquares := #odd filtering <~ #squared mapping.

"transforming drains and reductions"
sum := (#+ initialValue: 0) <~ oddSquares.
set := Set <~ oddSquares.

"result aggregation"
sum <~ oneToTen.
set <~ oneToTen.

Note, that #<~ is associative. Consider, for example, the expansion of the last expression.

(Set <~ (#odd filtering <~ #squared mapping)) <~ (Flattening <~ #(1 2 3 4 5 (6 7 8 (9 10)))).

Omitting (or changing) parenthesis does not change the result.

Set <~ #odd filtering <~ #squared mapping <~ Flattening <~ #(1 2 3 4 5 (6 7 8 (9 10))).

Implementing a new transformation is done by subclassing Transducer and adding factory methods to either BlockClosure and Symbol or Integer. To support the classical API style, a corresponding method has to be added to Reducer in the Reducers Classic API package as well.

## Concatenating Collections
Reducibles can be concatenated using #cat:

| cat |
cat := (-1 to: -10) cat: (1 to: 10).

To support concatenation, custom types should implement #cat: using the Catting transducer.

## Infinite Collections
Reducers can handle infinite reducibles, e.g., random number generators or arbitrary generator blocks.

| small |
"10 small random numbers"
small := 10 taking <~ [:x | x < 0.01] filtering <~ Random new.

| n naturals odds |
n := 0.
naturals := [n := n + 1].
"first 10 odd naturals"
odds := 10 taking <~ #odd filtering <~ naturals.

Implementation
The key concept of the Reducers model is to transform blocks/symbols (reducing functions) and let a source collection perform the reduction itself.
Thus, a virtual collection (reducer) does not change the source collection or its elements. Instead, it passes a transformed function (fn*) to the source collection if it receives the message #reduce: fn init: val. The transformation is performed by a transducer, e.g., Filtering and Mapping. Consider the following example.

| odds |
odds := #odd filtering <~ (1 to: 10).
(#+ initalValue: 0) <~ odds.

The first statement yields a reducer object that holds on the interval and a filtering transducer.
In the second statement, the reducing function #+ is transformed and passed to the interval.

(1 to: 10)
reduce: [:result :value | value odd ifTrue: [result + value] ifFalse: [result]]
init: 0.

The Reducers concept is based on the same-named Clojure library and ideas from the transducers concept in core Clojure. See:
http://clojure.com/blog/2012/05/08/reducers-a-library-and-model-for-collection-processing.html
http://clojure.com/blog/2012/05/15/anatomy-of-reducer.html
http://clojure.org/transducers