SRFI-171 General Discussion ​

The concept of reducers ​

The central part of transducers are 3-arity reducing procedures.

  • no arguments: Produces the identity of the reducer.
  • (result-so-far): completion. Returns result-so-far either with or without transforming it first.
  • (result-so-far input) combines result-so-far and input to produce a new result-so-far.

In the case of a summing + reducer, the reducer would produce, in arity order: 0, result-so-far, (+ result-so-far input). This happens to be exactly what the regular + does.

The concept of transducers ​

A transducer is a one-arity procedure that takes a reducer and produces a reducing function that behaves as follows:

  • no arguments: calls reducer with no arguments (producing its identity)
  • (result-so-far): Maybe transform the result-so-far and call reducer with it.
  • (result-so-far input) Maybe do something to input and maybe call the reducer with result-so-far and the maybe-transformed input.

A simple example is as following:

emacs-lisp
(list-transduce (tfilter odd?) + '(1 2 3 4 5))

This first returns a transducer filtering all odd elements, then it runs + without arguments to retrieve its identity. It then starts the transduction by passing + to the transducer returned by (tfilter odd?) which returns a reducing function. It works not unlike reduce from SRFI 1, but also checks whether one of the intermediate transducers returns a "reduced" value (implemented as a SRFI 9 record), which means the reduction finished early.

Because transducers compose and the final reduction is only executed in the last step, composed transducers will not build any intermediate result or collections. Although the normal way of thinking about application of composed functions is right to left, due to how the transduction is built it is applied left to right. (compose (tfilter odd?) (tmap sqrt)) will create a transducer that first filters out any odd values and then computes the square root of the rest.

State ​

Even though transducers appear to be somewhat of a generalisation of map and friends, this is not really true. Since transducers don’t know in which context they are being used, some transducers must keep state where their collection-specific counterparts do not. The transducers that keep state do so using hidden mutable state, and as such all the caveats of mutation, parallelism, and multi-shot continuations apply. Each transducer keeping state is clearly described as doing so in the documentation.

Naming ​

Reducers exported from the transducers module are named as in their SRFI-1 counterpart, but prepended with an r. Transducers also follow that naming, but are prepended with a t.