Intuitive Transducer in JavaScript

It’s been about two month since

Kyle

Simpson (getify) gave a JavaScript workshop at trivago. I had so much fun though out the week and I really enjoyed it with Kyle’s story telling and reasoning behind the materials.

I missed the last day of the workshop about functional programming so I decided to visit the material on Frontend Masters last night. He ended the course with a notion of transducing and I thought to myself

Maybe I’ll try to explain it with my own take.

So here we go.

What is transducing? Simply put, it’s a data transformation process without creating intermediate products. It’s like a pipeline. It’s your data on one end, and the pipeline transforms the data and produce your output on the other end.

Let’s say we have a set of data, and I’m using the example from Kyle’s example from the course so we have a reference to understand the concept better:

const list = [2,5,8,11,14,17,20]

and the transformation we’d like to perform is to output the sum of the data after incrementing one on each entry and then filtering out the even entries.

const output = list.map(addOne).filter(isOdd).reduce(sum) // 48

For each operation on the list, we produce a new list. And the new lists are the intermediate products. Transducing is a technique to avoid the intermediates and get that output straight out of one transformation. like this

const output = transducer(list) // 48

So how do we do that? We connect the operations together by making the operations share the same shape of input and output.

// we mash the operations into one Frankenstein function:p
const transducer = compose(map, filter, reduce)

Since we are reducing our list into a single number, let try to refactor our example to chain reduces.

const mapAddOneReducer = (result, item) => {
  result.push(item + 1)
  return result
}
const filterIsOddReducer = (result, item) => {
  if (item % 2 === 1) result.push(item)
  return result
}
const result = list
  .reduce(mapAddOneReducer,[])
  .reduce(filterIsOddReducer, [])
  .reduce((sum, v) => sum + v, 0)
// 48

Now if we look at the mapAddOneReducer , the incrementing responsibility is actually entangled in the function. We could extract it from mapAddOneReduce so we have function and all it does is to increment one. So let’s separate them.

const addOne = x => x + 1
const mapReducer = fn => (result, item) => {
  result.push(fn(item))
  return result
}

Same for filterIsOddReducer , let’s separate the predicate that determines whether a number is odd from the reducer.

const isOdd = x => x % 2 === 1
const filterReducer = predicate => (result, item) => {
  if (predicate(item)) result.push(item)
  return result
}

So the example becomes like this

const result = list
  .reduce(mapReducer(addOne), [])
  .reduce(filterReducer(isOdd), [])
  .reduce((sum, v) => sum + v, 0)
// 48

Much cleaner and the concerns are separated! But here are more separations we can do on mapReducer and filterReducer, right? Reducing is entangled with mapping and filtering! Let’s remove that itchiness.

const mapper = fn => reducer => (result, item) => {
  return reducer(result, fn(item))
}
const filterer = predicate => reducer => (result, item) => {
  if (predicate(item)) return reducer(result, item)
  return result
}

So now we can pass in a reducer to tell mapper and filterer how to reduce.

// a reducer
const pusher = (s, v) => {
  s.push(v)
  return s
}
const result = list
  .reduce(mapper(addOne)(pusher), [])
  .reduce(filterer(isOdd)(pusher), [])
  .reduce((sum, v) => sum + v, 0)
// 48

Now that we have a clear separation of concerns and we can see how similar mapper and filterer is. They both have the same input type and output type now. They both take in a function and produce a function that takes in a reducer and returns a reducer. So we can compose them like this.

const result = list
  .reduce(mapper(addOne)(filterer(isOdd)(pusher)),[])
  .reduce((sum, v) => sum + v, 0)
// 48

We can go one step further to properly compose the mapper and filterer.

import flowRight from 'lodash/flowRight'
const transformer = flowRight([
  mapper(addOne), 
  filterer(isOdd)
])
const result = list
  .reduce(transformer(pusher), [])
  .reduce((sum, v) => sum + v, 0)
// 48

We are so close to come up with a one-stop shop to transform the data! Let’s analyze transformation for a second.

Our current strategy is to generate a new list with transformer and then sum it up. The new list is a intermediate product that we want to avoid from the process. Now, instead of generating a new array and sum from it, why don’t we sum every step of the way while going through the list after transforming?

const result = list.reduce(
  transformer((sum, v) => sum + v, 0)
)

or

const sum = (sum, v) => sum + v
const result = list.reduce(transformer(sum), 0)) // 48

We did it! We have a single transformation to get the output that we are looking for. We have one reduce operation and get the output straight out of it without producing any product on the way. And that single transformation transformer(sum) is our transducer!

const transducer = transformer(sum)

or to be more clear

const transducer = flowRight([
  mapper(addOne), 
  filterer(isOdd)
])(sum)

Here you have it!

The whole process of finding the transducer is a little bizarre, but it actually makes sense if you look at it as a mathematical process. We are doing the same thing as we are handling algebra expressions. We break down the expression, find patterns, and reconstruct the expression to formulate the solution. It’s quite cool that we’re able to do that with JavaScript, right?

Any thought about functional programming and transducers? Drop me a comment or find me on twitter!