Transducer: A powerful function composition pattern

alias:: 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 ]

  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.

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

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

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).

  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 ]

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

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

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

Reducer

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

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

sum

  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
  }

map

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

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

filter

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

take

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

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

  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 ]

Transducer

Finally, we meet our protagonist
First re-examine the previous map implementation

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

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

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

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 compose(...fns) {
    return fns.reduceRight((acc, fn) => x => fn(acc(x)), x => x)
  }

Notice rfilter and the return type of rmap above:

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

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

  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)

into & transduce

However, how to use transducer ?

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

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

We need to implement iteration and collection using a reducer.

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

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

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 map = f => xs => ...

  type Transformer = (xs: T) => R

Flow

Fibonacci generator.

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

  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

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:

  type Transformer = (x: T) => T

Here is our implementation code:

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

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

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

  sum(range(11))
  // 55

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 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
  }

The execution of the function is right-associative.

transducer version

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

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

Reference

Transducers are Coming
Transducers - Clojure Reference

The above is the detailed content of Transducer: A powerful function composition pattern. For more information, please follow other related articles on the PHP Chinese website!