alias:: Transducer: A powerful function composition pattern
notebook:: Transducer: 一種強大的函數(shù)組合模式

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!