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中文網其他相關文章！
