alias:: Transducer：強(qiáng)大的函數(shù)組合模式
Notebook:: Transducer: 一個(gè)強(qiáng)大的函數(shù)組合模式

地圖和過濾器

map 的語義是“映射”，意思是對集合中的所有元素執(zhí)行一次轉(zhuǎn)換。

  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 ]

上面故意用了一個(gè)for語句來明確表達(dá)map的實(shí)現(xiàn)依賴于集合類型。
順序執(zhí)行；
立即評價(jià)，不偷懶。
讓我們看看過濾器：

  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 的實(shí)現(xiàn)也取決于具體的集合類型，當(dāng)前的實(shí)現(xiàn)要求 xs 為數(shù)組。
地圖如何支持不同的數(shù)據(jù)類型？例如，集合、地圖和自定義數(shù)據(jù)類型。
有一個(gè)常規(guī)的方式：依賴集合的接口（協(xié)議）。
不同的語言有不同的實(shí)現(xiàn)，JS在這方面原生支持相對較弱，但也是可行的：
使用 Symbol.iterator 進(jìn)行迭代。
使用 Object#contractor 獲取構(gòu)造函數(shù)。
那么我們?nèi)绾纬橄蟮刂С滞扑椭械牟煌瑪?shù)據(jù)類型？
模仿ramdajs庫，可以依賴自定義的@@transducer/step函數(shù)。

  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}

通過該方法，我們可以實(shí)現(xiàn)地圖、過濾等功能，更加軸向化。
關(guān)鍵是將構(gòu)造、迭代、集合等操作委托給具體的集合類，因?yàn)橹挥屑媳旧碇廊绾瓮瓿蛇@些操作。

  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}

撰寫

以上地圖和過濾器結(jié)合使用時(shí)會(huì)出現(xiàn)一些問題。

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

雖然只使用了5個(gè)元素，但是集合中的所有元素都會(huì)被遍歷。
每一步都會(huì)生成一個(gè)中間集合對象。
我們再次使用 compose 來實(shí)現(xiàn)這個(gè)邏輯

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

為了支持組合，我們以 curry 的形式實(shí)現(xiàn)了 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 ]

到目前為止，我們的實(shí)現(xiàn)在表達(dá)上是清晰簡潔的，但在運(yùn)行時(shí)卻很浪費(fèi)。

函數(shù)的形狀

變壓器

咖喱版本中的地圖功能是這樣的：

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

也就是說，map(x => ...) 返回一個(gè)單參數(shù)函數(shù)。

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

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

可以輕松組合具有單個(gè)參數(shù)的函數(shù)。
具體來說，這些函數(shù)的輸入是“數(shù)據(jù)”，輸出是處理后的數(shù)據(jù)，函數(shù)就是一個(gè)數(shù)據(jù)轉(zhuǎn)換器（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 是單參數(shù)函數(shù)，方便函數(shù)組合。

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

減速器

reducer 是一個(gè)二參數(shù)函數(shù)，可用于表達(dá)更復(fù)雜的邏輯。

  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]

拿

如何實(shí)施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 ]

傳感器

終于見到主角了
首先重新檢查之前的地圖實(shí)現(xiàn)

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

我們需要找到一種方法，將上面提到的依賴于數(shù)組（Array）的邏輯分離出來，抽象成一個(gè)Reducer。

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

構(gòu)造消失了，迭代消失了，元素的集合也消失了。
通過減速器，我們的映射僅包含其職責(zé)范圍內(nèi)的邏輯。
再看看過濾器

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

它其實(shí)是一個(gè)Transfomer，參數(shù)和返回值都是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)

進(jìn)入并轉(zhuǎn)換

但是，如何使用換能器？

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

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

我們需要使用reducer來實(shí)現(xiàn)迭代和收集。

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

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

現(xiàn)在可以工作了，我們還注意到迭代是“按需”的。雖然集合中有 100 個(gè)元素，但只迭代了前 10 個(gè)元素。
接下來我們將上面的邏輯封裝成一個(gè)函數(shù)。

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

  type Transformer = (xs: T) => R

流動(dòng)

斐波那契發(fā)生器。

假設(shè)我們有某種異步數(shù)據(jù)收集，例如異步無限斐波那契生成器。

  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

我們需要實(shí)現(xiàn)支持上述數(shù)據(jù)結(jié)構(gòu)的 into 函數(shù)。
把數(shù)組版本的代碼貼在旁邊作為參考：

  type Transformer = (x: T) => T

這是我們的實(shí)現(xiàn)代碼：

  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

相同的邏輯適用于不同的數(shù)據(jù)結(jié)構(gòu)。

訂單

細(xì)心的你可能會(huì)注意到，基于curry的compose版本和基于reducer的版本參數(shù)順序是不同的。

咖喱版

  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
  }

函數(shù)的執(zhí)行是右關(guān)聯(lián)的。

傳感器版本

  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：強(qiáng)大的函數(shù)組合模式的詳細(xì)內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！