Transducers

TL;DR

• map and filter apply atomic functions
• mapReducer and filterReducer build reducers using atomic functions
• mapTransducer and filterTransducer change reducers using atomic functions

A fold (or reduce) can be used as the performant functional-style equivalent to a raw imperative-style for loop to process a collection, potentially at the expense of becoming less expressive and less composable.

The more expressive operations, like map and filter, are nice because they take a simple atomic function and lift it to perform a richer operation. Those same functions can be used in the implementation of a reducer passed to fold but it has to take on multiple responsibilities.

Transducers are a (highly specific!) abstraction that use the same atomic functions to change a reducer:

Reducer :: (a, b) -> a
Transducer :: Reducer -> Reducer

A complex function implemented using chained Array#filter and Array#map will create intermediate values:

const filterThenMap = (items, pred, tr) =>
  // 🤔 two passes
  items.filter(pred).map(tr)

The same function implemented using Array#reduce has a single pass but uses a bespoke reducer:

const filterThenMap = (items, pred, tr) =>
  // 🤔 single pass but bespoke
  items.reduce(
    (acc, item) => pred(item) ? acc.concat([tr(item)]) : acc,
    []
  )

And using Array#reduce with transducers gets back to composition:

const filterThenMap = (items, pred, tr) =>
  // 👍 single pass with composition
  items.reduce(
    filterTransducer(pred)(mapReducer(tr)),
    []
  )

// REDUCERS: Builders for `reduce` functionality
// type Reducer = (a, b) => a

// TRANSDUCERS: Change a given reducer into a new reducer
// type Transducer = Reducer => Reducer

// filterReducer :: (fn) => Reducer
const filterReducer = (fn) =>
  (acc, item) => fn(item) ? acc.concat([item]) : acc

// filterTransducer :: (fn) => Transducer
const filterTransducer = (fn) => (reducer) =>
  (acc, item) => fn(item) ? reducer(acc, item) : acc

// mapReducer :: (fn) => Reducer
const mapReducer = (fn) =>
  (acc, item) => acc.concat([fn(item)])

// mapTransducer :: (fn) => Transducer
const mapTransducer = (fn) => (reducer) =>
  (acc, item) => reducer(acc, fn(item))

💡 Also, note that the transducer implementations are written in terms of another reducer so do not actually know about specific collection types! This means that the transducers can allow composition of the atomic functions over any collection data type with an underlying reducer.

const filterThenMapOverList = (items, pred, tr) =>
  // 👍 single pass with composition over list
  items.reduce(
    flow(
        filterTransducer(pred)
        mapTransducer(tr),
        (acc, item) => acc.concat(item), // 👈 core reducer
    ),
    []                                   // 👈 data structure
  )

const filterThenMapOverSet = (items, pred, tr) =>
  // 👍 single pass with composition over set
  items.reduce(
    flow(
        filterTransducer(pred)
        mapTransducer(tr),
        (acc, item) => acc.add(item), // 👈 core reducer
    ),
    new Set()                         // 👈 data structure
  )