dev-resources.site

for different kinds of informations.

Transducer: A powerful function composition pattern

Published at

1/13/2025

map & filter

The semantics of map is "mapping," which means performing a transformation on all elements in a set once.

const list = [1, 2, 3, 4, 5]

list.map(x => x + 1)
// [ 2, 3, 4, 5, 6 ]

function map(f, xs) {
  const ret = []
  for (let i = 0; i < xs.length; i++) {
    ret.push(f(xs[i]))
  }
  return ret
}

map(x => x + 1, [1, 2, 3, 4, 5])
// [ 2, 3, 4, 5, 6 ]

The above intentionally uses a for statement to clearly express that the implementation of map relies on the collection type.

Sequential execution;
Immediate evaluation, not lazy.

Let's look at filter:

function filter(f, xs) {
  const ret = []
  for (let i = 0; i < xs.length; i++) {
    if (f(xs[i])) {
      ret.push(xs[i])
    }
  }
  return ret
}

var range = n => [...Array(n).keys()]

filter(x => x % 2 === 1, range(10))
// [ 1, 3, 5, 7, 9 ]

Similarly, the implementation of filter also depends on the specific collection type, and the current implementation requires xs to be an array.

How can map support different data types? For example, Set , Map , and custom data types.

There is a conventional way: it relies on the interface (protocol) of the collection.

Different languages have different implementations, JS has relatively weak native support in this regard, but it is also feasible:

Iterate using Symbol.iterator .
Use Object#constractor to obtain the constructor.

So how do we abstractly support different data types in push ?

Imitating the ramdajs library, it can rely on the custom @@transducer/step function.

function map(f, xs) {
  const ret = new xs.constructor()  // 1. construction
  for (const x of xs) { // 2. iteration
    ret['@@transducer/step'](f(x))  // 3. collection
  }
  return ret
}

Array.prototype['@@transducer/step'] = Array.prototype.push
// [Function: push]

map(x => x + 1, [1, 2, 3, 4, 5])
// [ 2, 3, 4, 5, 6 ]

Set.prototype['@@transducer/step'] = Set.prototype.add
// [Function: add]

map(x => x + 1, new Set([1, 2, 3, 4, 5]))
// Set (5) {2, 3, 4, 5, 6}

By using this method, we can implement functions such as map , filter , etc., which are more axial.

The key is to delegate operations such as construction, iteration, and collection to specific collection classes, because only the collection itself knows how to complete these operations.

function filter(f, xs) {
  const ret = new xs.constructor()
  for (const x of xs) {
    if (f(x)) {
      ret['@@transducer/step'](x)
    }
  }
  return ret
}

filter(x => x % 2 === 1, range(10))
// [ 1, 3, 5, 7, 9 ]

filter(x => x > 3, new Set(range(10)))
// Set (6) {4, 5, 6, 7, 8, 9}

compose

There will be some issues when the above map and filter are used in combination.

range(10)
  .map(x => x + 1)
  .filter(x => x % 2 === 1)
  .slice(0, 3)
// [ 1, 3, 5 ]

Although only 5 elements are used, all elements in the collection will be traversed.
Each step will generate an intermediate collection object.

We use compose to implement this logic again

function compose(...fns) {
  return fns.reduceRight((acc, fn) => x => fn(acc(x)), x => x)
}

To support composition, we implement functions like map and filter in the form of curry .

function curry(f) {
  return (...args) => data => f(...args, data)
}

var rmap = curry(map)
var rfilter = curry(filter)

function take(n, xs) {
  const ret = new xs.constructor()
  for (const x of xs) {
    if (n <= 0) {
      break
    }
    n--
    ret['@@transducer/step'](x)
  }
  return ret
}
var rtake = curry(take)

take(3, range(10))
// [ 0, 1, 2 ]

take(4, new Set(range(10)))
// Set (4) {0, 1, 2, 3}

const takeFirst3Odd = compose(
  rtake(3),
  rfilter(x => x % 2 === 1),
  rmap(x => x + 1)
)

takeFirst3Odd(range(10))
// [ 1, 3, 5 ]

So far, our implementation is clear and concise in expression but wasteful in runtime.

The shape of the function

Transformer

The map function in version curry is like this:

const map = f => xs => ...

That is, map(x => ...) returns a single-parameter function.

type Transformer = (xs: T) => R

Functions with a single parameter can be easily composed.

Specifically, the input of these functions is "data", the output is the processed data, and the function is a data transformer (Transformer).

data ->> map(...) ->> filter(...) ->> reduce(...) -> result

function pipe(...fns) {
  return x => fns.reduce((ac, f) => f(ac), x)
}

const reduce = (f, init) => xs => xs.reduce(f, init)

const f = pipe(
  rmap(x => x + 1),
  rfilter(x => x % 2 === 1),
  rtake(5),
  reduce((a, b) => a + b, 0)
)

f(range(100))
// 25

Transformer is a single-parameter function, convenient for function composition.

type Transformer = (x: T) => T

Reducer

A reducer is a two-parameter function that can be used to express more complex logic.

type Reducer = (ac: R, x: T) => R

sum

// add is an reducer
const add = (a, b) => a + b
const sum = xs => xs.reduce(add, 0)

sum(range(11))
// 55

map

function concat(list, x) {
  list.push(x)
  return list
}

const map = f => xs => xs.reduce((ac, x) => concat(ac, f(x)), [])

map(x => x * 2)(range(10))
// [ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18 ]

filter

const filter = f => xs => xs.reduce((ac, x) => f(x) ? concat(ac, x) : ac, [])

filter(x => x > 3 && x < 10)(range(20))
// [ 4, 5, 6, 7, 8, 9 ]

take

How to implement take ? This requires reduce to have functionality similar to break .

function reduced(x) {
  return x && x['@@transducer/reduced'] ? x : { '@@transducer/reduced': true, '@@transducer/value': x }
}

function reduce(f, init) {
  return xs => {
    let ac = init
    for (const x of xs) {
      const r = f(ac, x)
      if (r && r['@@transducer/reduced']) {
        return r['@@transducer/value']
      }
      ac = r
    }
    return ac
  }
}

function take(n) {
  return xs => {
    let i = 0
    return reduce((ac, x) => {
      if (i === n) {
        return reduced(ac)
      }
      i++
      return concat(ac, x)
    }, [])(xs)
  }
}

take(4)(range(10))
// [ 0, 1, 2, 3 ]

Transducer

Finally, we meet our protagonist,

First re-examine the previous map implementation:

function map(f, xs) {
  const ret = []
  for (let i = 0; i < xs.length; i++) {
    ret.push(f(xs[i]))
  }
  return ret
}

We need to find a way to separate the logic that depends on the array (Array) mentioned above and abstract it into a Reducer .

function rmap(f) {
  return reducer => {
    return (ac, x) => {
      return reducer(ac, f(x))
    }
  }
}

The construction disappeared, the iteration disappeared, and the collection of elements also disappeared.

Through a reducer , our map only contains the logic within its responsibilities.

Take another look at filter:

function rfilter(f) {
  return reducer => (ac, x) => {
    return f(x) ? reducer(ac, x) : ac
  }
}

Notice rfilter and the return type of rmap above:

reducer => (acc, x) => ...

It is actually a Transfomer , with both parameters and return values being Reducer , it is Transducer .

Transformer is composable, so Transducer is also composable.

function rtake(n) {
  return reducer => {
    let i = 0
    return (ac, x) => {
      if (i === n) {
        return reduced(ac)
      }
      i++
      return reducer(ac, x)
    }
  }
}

into & transduce

However, how to use transducer ?

compose
// [Function: compose]

var tf = compose(
  rmap(x => x + 1),
  rfilter(x => x % 2 === 1),
  rtake(5)
)
tf
// [Function (anonymous)]

We need to implement iteration and collection using a reducer.

const collect = (ac, x) => {
  ac.push(x)
  return ac
}

const reducer = tf(collect)
reduce(reducer, [])(range(100))
// [ 1, 3, 5, 7, 9 ]

It can work now, and we also noticed that the iteration is "on-demand".

Although there are 100 elements in the collection, only the first 10 elements were iterated.

Next, we will encapsulate the above logic into a function.

const collect = (ac, x) => {
  ac.push(x)
  return ac
}

function into(init, tf) {
  const reducer = tf(collect)
  return reduce(reducer, init)
}

into([], compose(
  rmap(x => x + 1),
  rfilter(x => x % 2 === 1),
  rtake(8)
))  (range(100))
// [ 1, 3, 5, 7, 9, 11, 13, 15 ]

Flow

Fibonacci generator.

Suppose we have some kind of asynchronous data collection, such as an asynchronous infinite Fibonacci generator.

function sleep(n) {
  return new Promise(r => setTimeout(r, n))
}

async function *fibs() {
  let [a, b] = [0, 1]
  while (true) {
    await sleep(10)
    yield a
    ;[a, b] = [b, a + b]
  }
}

const s = fibs()
async function start() {
  let i = 0
  for await (const item of s) {
    console.log(item)
    i++
    if (i > 10) {
      break
    }
  }
}

start()

Promise [Promise] {}
0
1
1
2
3
5
8
13
21
34
55

We need to implement the into function that supports the above data structures.

Post the array version of the code next to it as a reference:

const collect = (ac, x) => {
  ac.push(x)
  return ac
}

function into(init, tf) {
  const reducer = tf(collect)
  return reduce(reducer, init)
}

Here is our implementation code:

const collect = (ac, x) => {
  ac.push(x)
  return ac
}

const reduce = (reducer, init) => {
  return async iter => {
    let ac = init
    for await (const item of iter) {
      if (ac && ac['@@transducer/reduced']) {
        return ac['@@transducer/value']
      }
      ac = reducer(ac, item)
    }
    return ac
  }
}

function sinto(init, tf) {
  const reducer = tf(collect)
  return reduce(reducer, init)
}

The collection operation is the same, the iteration operation is different.

const task = sinto([], compose(
  rmap(x => x + 1),
  rfilter(x => x % 2 === 1),
  rtake(8)
))

task(fibs()).then(res => {
  console.log(res)
})

// Promise [Promise] {}
// 1,3,9,35,145,611,2585,10947

The same logic applies to different data structures.

Orders

You, who are attentive, may notice that the parameter order of the compose version based on curry and the version based on reducer are different.

curry version

const map = f => xs => xs.map(f)

var tap = msg => x => {
  console.log(msg)
  return x
}

compose(
  map(tap('process 1')),
  map(tap('process 2')),
  map(tap('process 3'))
) (range(5))

process 3
process 3
process 3
process 3
process 3
process 2
process 2
process 2
process 2
process 2
process 1
process 1
process 1
process 1
process 1
[ 0, 1, 2, 3, 4 ]

The execution of the function is right-associative.

transducer version

const fmap = f => reducer => (ac, x) => {
  return reducer(ac, f(x))
}

const collect = (ac, x) => {
  ac.push(x)
  return ac
}

function into(init, tf) {
  const reducer = tf(collect)
  return xs => xs.reduce(reducer, init)
}

into([], compose(
  fmap(tap('process 1')),
  fmap(tap('process 2')),
  fmap(tap('process 3'))
)) (range(5))

process 1
process 2
process 3
process 1
process 2
process 3
process 1
process 2
process 3
process 1
process 2
process 3
process 1
process 2
process 3
[ 0, 1, 2, 3, 4 ]