Transducer：强大的函数组合模式

alias:: Transducer：强大的函数组合模式
Notebook:: Transducer: 一个强大的函数组合模式

地图和过滤器

map 的语义是“映射”，意思是对集合中的所有元素执行一次转换。

  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 ]

上面故意用了一个for语句来明确表达map的实现依赖于集合类型。
顺序执行；
立即评价，不偷懒。
让我们看看过滤器：

  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 ]

同样，filter 的实现也取决于具体的集合类型，当前的实现要求 xs 为数组。
地图如何支持不同的数据类型？例如，集合、地图和自定义数据类型。
有一个常规的方式：依赖集合的接口（协议）。
不同的语言有不同的实现，JS在这方面原生支持相对较弱，但也是可行的：
使用 Symbol.iterator 进行迭代。
使用 Object#contractor 获取构造函数。
那么我们如何抽象地支持推送中的不同数据类型？
模仿ramdajs库，可以依赖自定义的@@transducer/step函数。

  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}

通过该方法，我们可以实现地图、过滤等功能，更加轴向化。
关键是将构造、迭代、集合等操作委托给具体的集合类，因为只有集合本身知道如何完成这些操作。

  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}

撰写

以上地图和过滤器结合使用时会出现一些问题。

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

虽然只使用了5个元素，但是集合中的所有元素都会被遍历。
每一步都会生成一个中间集合对象。
我们再次使用 compose 来实现这个逻辑

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

为了支持组合，我们以 curry 的形式实现了 map 和 filter 等功能。

  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 ]

到目前为止，我们的实现在表达上是清晰简洁的，但在运行时却很浪费。

函数的形状

变压器

咖喱版本中的地图功能是这样的：

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

也就是说，map(x => ...) 返回一个单参数函数。

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

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

可以轻松组合具有单个参数的函数。
具体来说，这些函数的输入是“数据”，输出是处理后的数据，函数就是一个数据转换器（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 是单参数函数，方便函数组合。

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

减速器

reducer 是一个二参数函数，可用于表达更复杂的逻辑。

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

和

  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]

拿

如何实施take？这需要reduce具有类似于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 ]

传感器

终于见到主角了
首先重新检查之前的地图实现

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

我们需要找到一种方法，将上面提到的依赖于数组（Array）的逻辑分离出来，抽象成一个Reducer。

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

构造消失了，迭代消失了，元素的集合也消失了。
通过减速器，我们的映射仅包含其职责范围内的逻辑。
再看看过滤器

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

注意上面的 rfilter 和 rmap 的返回类型：

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

它其实是一个Transfomer，参数和返回值都是Reducer，它就是Transducer。
Transformer 是可组合的，因此 Transducer 也是可组合的。

  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}

我们需要使用reducer来实现迭代和收集。

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

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

现在可以工作了，我们还注意到迭代是“按需”的。虽然集合中有 100 个元素，但只迭代了前 10 个元素。
接下来我们将上面的逻辑封装成一个函数。

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

  type Transformer = (xs: T) => R

流动

斐波那契发生器。

假设我们有某种异步数据收集，例如异步无限斐波那契生成器。

  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

我们需要实现支持上述数据结构的 into 函数。
把数组版本的代码贴在旁边作为参考：

  type Transformer = (x: T) => T

这是我们的实现代码：

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

集合操作相同，迭代操作不同。

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

  sum(range(11))
  // 55

相同的逻辑适用于不同的数据结构。

订单

细心的你可能会注意到，基于curry的compose版本和基于reducer的版本参数顺序是不同的。

咖喱版

  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 ]

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

参考

换能器来了
传感器 - Clojure 参考

以上是Transducer：强大的函数组合模式的详细内容。更多信息请关注PHP中文网其他相关文章！