Transducer

Posted on 2020-10-03 In JavaScript

Reducer

Reducer 將多個 input fold 成一個 output.

const add = (a, b) => a + b
const multiply = (a, b) => a * b
const concatString = (a, b) => a + b
const concatArray = (a, b) => [...a, ...b]

Transducer

Transducer 做的事情大致相同,但是與普通的 reducer 不同的是,它可以通過多個 function 組合而成.而普通的 reducer 不能組合,因爲他們接受兩個參數,但是只返回一個值,所以不能將這次的結果傳入下一個 reducer:

// reducer
f: (a, c) => a
g: (a, c) => a

// transducer
f: (reducer) => reducer
g: (reducer) => reducer

Why Transducers?

儅我們處理數據時,將處理過程拆分成相互獨立,然後組合的步驟會非常有用.假設現在有一個非常大的數據集,現在需要對數據集處理某些操作,你可能會這樣做:

const friends = [
  { id: 1, name: "Sting", nearMe: true },
  { id: 2, name: "Radiohead", nearMe: true },
  { id: 3, name: "NIN", nearMe: false },
  { id: 4, name: "Echo", nearMe: true },
  { id: 5, name: "Zeppelin", nearMe: false },
]
const isNearMe = ({ nearMe }) => nearMe
const getName = ({ name }) => name

const results = friends.filter(isNearMe).map(getName)

console.log(results) // => ["Sting", "Radiohead", "Echo"]

上面的例子存在著一定的問題:只能處理 array;如果存在從網絡上來的無限數據流,該如何處理?

每次在 array 上使用.語法時,JavaScript 都會構造一個全新的 intermediate array,如果你的 array 非常龐大,這時的性能會出現指數級的下降.若使用 transducer,則可以將每個 item 在 pipe 中傳輸,無需建立中間對象,從而節省了大量的時間和内存.

Example

下面的代碼暫時未實現具體的操作,但是可以先觀察 transducer 是如何構建的.

const friends = [
  { id: 1, name: "Sting", nearMe: true },
  { id: 2, name: "Radiohead", nearMe: true },
  { id: 3, name: "NIN", nearMe: false },
  { id: 4, name: "Echo", nearMe: true },
  { id: 5, name: "Zeppelin", nearMe: false },
]
const isNearMe = ({ nearMe }) => nearMe
const getName = ({ name }) => name

const getFriendsNearMe = compose(filter(isNearMe), map(getName))

const results2 = toArray(getFriendsNearMe, friends)

Transducer 在需要使用並給它傳遞數據時才會執行,也就是上述代碼的toArray()部分,你可以自己實現 transducer 的轉換結果.
Transducer 可以映射各種類型,例如

{x, y, z} -> {x, y, z}
{x, y ,z} -> {x, z}
{x, y, z} -> {x, y, z, xx, yy, zz}

假設我們現在需要讓一個 array 中的數字翻倍,我們可以這麽實現:

const double = (x) => x * 2
const arr = [1, 2, 3]

const result = arr.map(double)

在上述例子中,arr 是一個可枚舉對象,map 將每個對象單獨進行 double 處理,然後將所有的值纍加到新的 array 中.
我們還可以實現新的效果:

const isEven = (x) => x % 2 === 0
const double = (x) => x * 2
const arr = [1, 2, 3, 4, 5, 6]

const result = arr.filter(isEven).map(double)

console.log(result)

但是,處理無限數據流時會發生什麽?
數組是不能無限長的,在數組的處理中,你必須將整個迭代成一個集合,才能進行下一步的處理.這種限制就會導致性能降低,因爲需要創建一個中間數組,并且為每個操作迭代一次新的集合.就用上述的例子來説,首先有一個過濾單數的操作,然後有一個倍增的操作.必須先在過濾操作中將所有的元素進行過濾,然後再在 double 中執行所有的元素,才能夠拿到你想要的數據.
一種處理方法是將每個值單獨映射,一次通過一個值,這樣就避免了每次生成一個映射集合,并且隨時能夠通過值來發出終止信號:

Pull: lazy evaluation: 直到用戶要求取下一個值時,才會拿出下一個值.如Iterable.
Push: eager evaluation: 每次拿出一個值,然後傳入 reducer 中,生成新值.如Array.reduce()

Transducer 不關心你使用的是哪種方式,也不關心數據的具體結構,他們只是簡單的調用傳入的 reducer 並纍加新值.實際上就是一個 Higher Order Reducer,它的類型大致為:

1 2	reducer = (accumulator, current) => accumulator transducer = (reducer) => reducer

大多數 transducer 需要使用一定的參數以實現特定的功能,所以一個 map transducer 也許類型為這樣:

map = (transform) => (reducer) => reducer;

// another way
map = ((a) => b) => (step) => reducer;

map 接受一個 mapping function(transform),一個 reducer(step)然後返回一個新的 reducer.現在來看一些簡單的例子.

Naive Examples

const compose =
  (...fns) =>
  (x) =>
    fns.reduceRight((y, f) => f(y), x)
const map = (f) => (step) => (a, c) => step(a, f(c))
const filter = (predicate) => (step) => (a, c) => predicate(c) ? step(a, c) : a

const isEven = (n) => n % 2 === 0
const double = (n) => n * 2

const doubleEvens = compose(filter(isEven), map(double)) // also a transducer
const arrayConcat = (a, c) => a.concat([c]) // step
const xform = doubleEvens(arrayConcat) // a reducer

const result = [1, 2, 3, 4, 5, 6].reduce(xform, []) // [4, 8, 12]

在這個例子中,map 就是一個 transducer,你還能這樣使用:

const double = (x) => x * 2
const doubleMap = map(double) // double is a transform
const step = (a, c) => console.log(c)

doubleMap(step)(0, 4) // 8
doubleMap(step)(0, 21) // 42

其中,0 代表 reducer 的初始值,step 函數本該是一個 reducer,但是方便演示就將他寫成一個 logger.這種技巧也可以在單元測試中作斷言使用.