DEV Community

Cover image for Transducer: A powerful function composition pattern
qjun
qjun

Posted on • Edited on

Transducer: A powerful function composition pattern

notebook:: Transducer: 一种强大的函数组合模式

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 ]
Enter fullscreen mode Exit fullscreen mode
function map(f, xs) {
  const ret = []
  for (let i = 0; i < xs.length; i++) {
    ret.push(f(xs[i]))
  }
  return ret
}
Enter fullscreen mode Exit fullscreen mode
map(x => x + 1, [1, 2, 3, 4, 5])
// [ 2, 3, 4, 5, 6 ]
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode
var range = n => [...Array(n).keys()]
Enter fullscreen mode Exit fullscreen mode
filter(x => x % 2 === 1, range(10))
// [ 1, 3, 5, 7, 9 ]
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode
Array.prototype['@@transducer/step'] = Array.prototype.push
// [Function: push]
Enter fullscreen mode Exit fullscreen mode
map(x => x + 1, [1, 2, 3, 4, 5])
// [ 2, 3, 4, 5, 6 ]
Enter fullscreen mode Exit fullscreen mode
Set.prototype['@@transducer/step'] = Set.prototype.add
// [Function: add]
Enter fullscreen mode Exit fullscreen mode
map(x => x + 1, new Set([1, 2, 3, 4, 5]))
// Set (5) {2, 3, 4, 5, 6}
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode
filter(x => x % 2 === 1, range(10))
// [ 1, 3, 5, 7, 9 ]
Enter fullscreen mode Exit fullscreen mode
filter(x => x > 3, new Set(range(10)))
// Set (6) {4, 5, 6, 7, 8, 9}
Enter fullscreen mode Exit fullscreen mode

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 ]
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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

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

Enter fullscreen mode Exit fullscreen mode
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)
Enter fullscreen mode Exit fullscreen mode
take(3, range(10))
// [ 0, 1, 2 ]
Enter fullscreen mode Exit fullscreen mode
take(4, new Set(range(10)))
// Set (4) {0, 1, 2, 3}
Enter fullscreen mode Exit fullscreen mode
const takeFirst3Odd = compose(
  rtake(3),
  rfilter(x => x % 2 === 1),
  rmap(x => x + 1)
)

takeFirst3Odd(range(10))
// [ 1, 3, 5 ]
Enter fullscreen mode Exit fullscreen mode

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 => ...
Enter fullscreen mode Exit fullscreen mode

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

type Transformer = (xs: T) => R
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode
function pipe(...fns) {
  return x => fns.reduce((ac, f) => f(ac), x)
}
Enter fullscreen mode Exit fullscreen mode
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
Enter fullscreen mode Exit fullscreen mode

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

type Transformer = (x: T) => T
Enter fullscreen mode Exit fullscreen mode

Reducer

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

type Reducer = (ac: R, x: T) => R
Enter fullscreen mode Exit fullscreen mode

sum

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

sum(range(11))
// 55
Enter fullscreen mode Exit fullscreen mode

map

function concat(list, x) {
  list.push(x)
  return list
}
Enter fullscreen mode Exit fullscreen mode
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 ]
Enter fullscreen mode Exit fullscreen mode

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 ]
Enter fullscreen mode Exit fullscreen mode

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
  }
}
Enter fullscreen mode Exit fullscreen mode
function take(n) {
  return xs => {
    let i = 0
    return reduce((ac, x) => {
      if (i === n) {
        return reduced(ac)
      }
      i++
      return concat(ac, x)
    }, [])(xs)
  }
}
Enter fullscreen mode Exit fullscreen mode
take(4)(range(10))
// [ 0, 1, 2, 3 ]
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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))
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

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
  }
}
Enter fullscreen mode Exit fullscreen mode

Notice rfilter and the return type of rmap above:

reducer => (acc, x) => ...
Enter fullscreen mode Exit fullscreen mode

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)
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

into & transduce

However, how to use transducer ?

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

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 ]
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode
into([], compose(
  rmap(x => x + 1),
  rfilter(x => x % 2 === 1),
  rtake(8)
))  (range(100))
// [ 1, 3, 5, 7, 9, 11, 13, 15 ]
Enter fullscreen mode Exit fullscreen mode

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]
  }
}
Enter fullscreen mode Exit fullscreen mode
const s = fibs()
async function start() {
  let i = 0
  for await (const item of s) {
    console.log(item)
    i++
    if (i > 10) {
      break
    }
  }
}

start()

Enter fullscreen mode Exit fullscreen mode
Promise [Promise] {}
0
1
1
2
3
5
8
13
21
34
55
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode
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 ]
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode
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 ]
Enter fullscreen mode Exit fullscreen mode

Reference

Heroku

This site is built on Heroku

Join the ranks of developers at Salesforce, Airbase, DEV, and more who deploy their mission critical applications on Heroku. Sign up today and launch your first app!

Get Started

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay