/ JavaScript

細說轉化者(Transducers):第一部

This article is a translated version in Traditional Chinese, the original article is Transducers Explained: Part 1 written by simplectic.com.


使用JavaScript來介紹轉化器。我們將從歸納(reducing)陣列開始,一直到定義轉換成為轉化器,接著漸進的介紹轉化器以及如何使用轉化。最後會總結我們的所學,接著是未來的文章,還有相關參考的連結,包括現有的轉化器函示庫。

轉化器...

到底是什麼?

直接看來源

轉化器是一種可組合的演算轉變。獨立於輸入及輸出的前後關係,只有指出個別元素的轉變本質。因為轉化器從其輸入及輸出中解耦(decoupled)出來,所以可以被用在許多不同的程序 - 集合(collections)、串流(streams)、頻道(channels)、觀察者(observables)等等。轉化器會直接地組合,不會意識到輸入或建立中介的聚集。

嗯...

我不明白

我們來看些程式碼。當你使用轉化器,"演算的轉變"已經定義,至少部分是,透過一種函示,類似於你傳遞到歸納的函式。 Clojure的文件 稱這些函示為歸納函式。這是什麼?很好,讓我們從Array#reduce開始。你可以從MDN找到定義。

歸納

reduce()接受一個函式,函式的參數為「累加值」及「每個陣列值」(順序從左到右提供),最終歸納回傳一個「結果值」。

你可以閱讀文件來取得更多解釋,我這裡將示範幾個快速範例,它們都蠻相似。

function sum(result, item){
  return result + item;
}

function mult(result, item){
  return result * item;
}

// 10 (=1+2+3+4)
var summed = [2,3,4].reduce(sum, 1);

// 24 (=1*2*3*4)
var multed = [2,3,4].reduce(mult, 1);

上述程式碼中的歸納函示summult。它們作為reduce函示的參數,加上初始值參數,兩者都用1作為初始值參數。"輸入來源"是個陣列[2, 3, 4],"輸出來源"則是個新陣列,從reduce內部中實作產出。

幾點有關reduce的重要事情:

  1. 開始於一個初始值
  2. 歸納函數一次只處理一項
  • 第一次的result參數值就是開始時帶入的初始值
  • 每回執行後的結果,會作為下一回執行的result
  1. 最後輸出的是最後一回執行完的result值。

注意,這兩個案例中,歸納函示(帶入reduce的第一個參數)為外部函示。只有初始值或前次執行後的結果會帶入函示。第二個參數值是個獨特的元素,通過某回的處理才傳入。這裡,歸納函示會迭代陣列中的每個元素,稍後我們會看到其他迭代方法。我們裡用歸納函示來描繪出「轉化的本質」

轉化器

讓我們在一個轉化器中,形式化(formalize)這些步驟。

var transformer = function(reducingFunction){
  return {
    // 1. 開始於一個初始值
    init: function(){
      return 1;
    },

    // 2. 一次輸入一個項目,透過歸納函示,每次結果會傳遞到下一次的迭代
    step: reducingFunction,

    // 3. 最後輸出結果值
    result: function(result){
      return result;
    }
  }
}

我們建立一個物件,包裝任何的歸納函示,命名為step,並且提供init來初始轉化器,最後用result來轉換結果值成為我們需要的輸出。注意,在這篇文章中,我們將專注在step函式。未來的文章會更深入探討initresult。現在,你可以將想像這些方法(methods)用來幫助管理轉化器的生命週期:init用來初始化任何資源,step迭代,result用來清理結尾。

現在,將轉化器用在歸納函示。

var input = [2,3,4];

var xf = transformer(sum);
var output = input.reduce(xf.step, xf.init());
// output = 10 (=1+2+3+4)

var xf = transformer(mult);
var output = input.reduce(xf.step, xf.init());
// output = 24 (=1*2*3*4)

因為最終目標是將轉化器從輸入、輸出中解耦(decouple)出來,所以我們將reduce另外定義一個函式。

function reduce(xf, init, input){
  var result = input.reduce(xf.step, init);
  return xf.result(result);
}

為了使用這個reduce函式,我們傳入一個轉化器、初始值及輸入來源。函式內的實作,使用step函式帶入陣列的歸納函式,接著將歸納函式的結果值result作為輸出。這內部實作仍然假設輸入是個陣列。稍後我們將移除這個架設。

我們也接受init參數病傳入reduce。我們可以使用轉化器的init函式,但我們處於歸納階段,希望能保留更改初始值的能力。實踐中,只當初始值未提供時,才會用轉化器的init函式。

使用新的歸納函式很類似於我們先前所做。

var input = [2,3,4];
var xf = transformer(sum);
var output = reduce(xf, xf.init(), input);
// output = 10 (=1+2+3+4)

var input = [2,3,4];
var xf = transformer(mult);
var output = reduce(xf, xf.init(), input);
// output = 24 (=1*2*3*4)

我們可以透過帶入初始值來改變它。

var input = [2,3,4];
var xf = transformer(sum);
var output = reduce(xf, 2, input);
// output = 11 (=2+2+3+4)

var input = [2,3,4];
var xf = transformer(mult);
var output = reduce(xf, 2, input);
// output = 48 (=2*2*3*4)

我們的reduce函式目前要求帶入一個轉化器。自從內部不曾使用initresult經常是一致的函式,一個函式直接回傳單一引數,我們將定義一個補助函式來將歸納函式轉換成一個轉化器,然後用在reduce

function reduce(xf, init, input){
  if(typeof xf === 'function'){
    // 確保是個轉化器
    xf = wrap(xf);
  }
  var result = input.reduce(xf.step, init);
  return xf.result(result);
}


function wrap(xf){
  return {
    // 1. 我們要求init是個函式參數,所以這裡就不需要
    init: function(){
      throw new Error('init not supported');
    },

    // 2.  一次輸入一個項目,透過歸納函示,每次結果會傳遞到下一次的迭代
    step: xf,

    // 3. 最後輸出結果值
    result: function(result){
      return result;
    }
  }
}

我們檢查了xf參數是否為函式。如果是,我們假設它是個step函式,並且呼叫wrap函式將它轉換成一個轉化器。接著我們用歸納函式來處理它,就如先前所作。

現在我們可以直接傳入歸納函式到reduce之中。

var input = [2,3,4];
var output = reduce(sum, 1, input);
// output = 10 (=1+2+3+4)

var input = [2,3,4];
var output = reduce(mult, 2, input);
// output = 48 (=2*2*3*4)

如果想要,我們仍然可以傳入轉化器,

var input = [2,3,4];
var xf = wrap(sum);
var output = reduce(xf, 2, input);
// output = 11 (=2+2+3+4)

var input = [2,3,4];
var xf = wrap(mult);
var output = reduce(xf, 1, input);
// output = 24 (=1*2*3*4)

注意到我們外部地使用wrap函式將我們既已的歸納函式建立出一個轉化器。這個在操作轉化器時很常見:你將轉化定義成簡單函式,讓轉化器函式庫處理轉換成轉化器。

花式的陣列拷貝

目前為止,我們在努力於數值上,如初始值和算數的歸納函式。這個並非必要的,我們也可以將reduce用在陣列中。

function append(result, item){
  result.push(item);
  return result;
}

var input = [2,3,4];
var output = reduce(append, [], input);
// output = [2, 3, 4]

我們定義一個步進函式append,用來將一個項目附加到陣列中,並將結果傳回。利用它,我們可以使用reduce函式來建立一個新的副本陣列。

有沒有很感動?我知道。還好。當它變有趣的時後,就是當你加入一種能力,能夠在附加項目到陣列前,將項目進行轉換。

孤獨的數字

假設我們想要將每一個值都加1。定義一個函式來將一個值加1。

function plus1(item){
  return item + 1;
}

現在,使用這個函式建立一個轉化器,在step函式中轉換各個項目。

var xfplus1 = {
  init: function(){
    throw new Error('不需要init');
  },
  step: function(result, item){
    var plus1ed = plus1(item);
    return append(result, plus1ed);
  },
  result: function(result){
    return result;
  }
}

我們可以使用轉化器來逐步通過得到結果。

var xf = xfplus1;
var init = [];
var result = xf.step(init, 2);
// [3] (=append([], 2+1)))

result = xf.step(result, 3);
// [3,4] (=append([3], 3+1)))

result = xf.step(result, 4);
// [3,4,5] (=append([3,4], 4+1)))

var output = xf.result(result);
// [3,4,5]

我們用轉化器來逐步通過項目並附加每一個遞增後的項目到輸出陣列。

如果我們真正想要的是這些遞增項目的加總值呢?
我們可以用reduce

var output = reduce(sum, 0, output);
// 12 (=0+3+4+5)

的確可用,但很不幸的事,我們需要建立一個中間陣列才能得到最終答案。我們可以做得更好嗎?

事實上可以。看一下上面的xfplus1。如果我們將append的呼叫替換成sum的呼叫,並將初始值帶入數字0,我們可以定義一個轉化器直接用來加總每一個項目,並且不需要額外建立中間聚合的陣列。

但是,也有可能的情況是,我們希望看到中間陣列。這之中的改變只有將append改成sum,很樂於見到有個函式可以用來定義轉化而不管轉化器過去合併的結果值。

就這樣做。

var transducerPlus1 = function(xf){
  return {
    init: function(){
      return xf.init();
    },
    step: function(result, item){
      var plus1ed = plus1(item);
      return xf.step(result, plus1ed);
    },
    result: function(result){
      return xf.result(result);
    }
  }
}

這個函式接受一個轉化器xf作為參數,並且用它來傳回另一個轉化器,新的轉化器先用plus1轉化項目後再委派到原有的轉化器。我們完全地利用step函式來定義新的轉化,新的轉化器直接使用xfinitresult。它在新包裝的step函式內先用plus1轉化項目,然後才呼叫原本轉化器的step函式。

轉化者

我們建立了第一個轉化者。一種接受現有轉化器並回傳新轉化器的函式,新轉化器在某些地方上改變了轉化,委派額外的控制到新轉化器。

開始使用吧!首先,用我們的轉化器來重新迭代先前範例。

var stepper = wrap(append);
var init = [];
var transducer = transducerPlus1;
var xf = transducer(stepper);
var result = xf.step(init, 2);
// [3] (=append([], 2+1)))

result = xf.step(result, 3);
// [3,4] (=append([3], 3+1)))

result = xf.step(result, 4);
// [3,4,5] (=append([3,4], 4+1)))

var output = xf.result(result);
// [3,4,5]

同樣可以運作。很好。唯一的差異是轉化器xf的建立。我們用wrap來轉換append成為一個轉化器stepper,接著用我們的轉化者包裝stepper傳回新的plus1轉化器。接著使用xf轉化,如同我們先前所作,逐步通過每個項目並取得結果值。

中間聚合

這裡是事情變有趣的地方:我們可以用相同的轉化者來得到最終要的加總值,不需要額外的中間陣列,只要改變stepper及初始值。

var stepper = wrap(sum);
var init = 0;
var transducer = transducerPlus1;
var xf = transducer(stepper);
var result = xf.step(init, 2);
// 3 (=sum(0, 2+1)))

result = xf.step(result, 3);
// 7 (=sum(3, 3+1)))

result = xf.step(result, 4);
// 12 (=sum(7, 4+1)))

var output = xf.result(result);
// 12

一次迭代中我們就得到答案,不需要計算中間陣列。在前述範例中只有兩個改變:

  1. 當建立stepper時,包裝了sum而不是append
  2. 初始值是個數字0而不是空陣列[]

就這樣。其它都一樣。

注意到只有stepper轉化器會察覺result的型別。當包裝sum時會是個數字,包裝append時會是個陣列。初始值的型別與result的型別是一致的。item可以是任何東西,只要stepper知道如何與新的項目進行合併並回傳新的合併值,而下一回迭代也可以進行合併。

這些屬性允許定義轉化器獨立於輸出來源。

可能變更糟

如果我們想要個plus2呢?什麼需要改變?我們可以定義一個新的transducerPlus2就像是transducerPlus1。花點時間看看transducerPlus1並決定什麼需要改變。

我們可以做的更好嗎?

結果是所有東西都一樣,除了轉化的函式中呼叫plus2取而代之plus1

讓我們抽出plus1並將它當作函式傳入f

var map = function(f){
  return function(xf){
    return {
      init: function(){
        return xf.init();
      },
      step: function(result, item){
        var mapped = f(item);
        return xf.step(result, mapped);
      },
      result: function(result){
        return xf.result(result);
      }
    }
  }
}

我們定義了一個對應轉化者。讓我們用它來步進通過轉化。

function plus2(input){
  return input+2;
}
var transducer = map(plus2);
var stepper = wrap(append);
var xf = transducer(stepper);
var init = [];
var result = xf.step(init, 2);
// [4] (=append([], 2+2)))

result = xf.step(result, 3);
// [4,5] (=append([4], 3+2)))

result = xf.step(result, 4);
// [4,5,6] (=append([4,5], 4+1)))

var output = xf.result(result);
// [4,5,6]

相較這個範例與先前的plus1above。唯一差異是轉化者的產生利用了map。我們可以同樣地用map(plus1)來建立plus1轉化者。雖然transducerPlus1短命,但希望能夠描述到關鍵點。

轉化

先前範例描述了如何使用轉化者來手動地轉化一個系列的輸入。讓我們來穿透
它。

首先,我們透過呼叫一個轉化器來初始一個轉化過程並定義我們初始值。

var transducer = map(plus1);
var stepper = wrap(append);
var xf = transducer(stepper);
var init = [];

接著透過歸納函式xf.step來步進通過每個輸入項目,使用初始值作為第一個resultstep函式中,最後傳回結果值,通過所有接下來項目的step函式呼叫。

var result = xf.step(init, 2);
// [3] (=append([], 2+1)))

result = xf.step(result, 3);
// [3,4] (=append([3], 3+1)))

result = xf.step(result, 4);
// [3,4,5] (=append([3,4], 4+1)))

最終使用xf.result取得結果值。

var output = xf.result(result);
// [3,4,5]

你可能注意到這個非常相似於我們較早實作的reduce實作。事實上,沒錯。我們可以封裝這個程序到一個新函式transduce之中。

function transduce(transducer, stepper, init, input){
  if(typeof stepper === 'function'){
    // 確保我們有個轉化器
    stepper = wrap(stepper);
  }

  // 傳入stepper來建立轉換器
  var xf = transducer(stepper);

  // xf 現在是個轉化器
  // 現在可以利用上述定義的reduce進行迭代並轉化輸入
  return reduce(xf, init, input);
}

如同reduce,我們確保stepper是個轉化器。接著透過傳入stepper到轉化者來建立新的轉化器。最後使用reduce來迭代、轉化結果。

開始使用!

var transducer = map(plus1);
var stepper = append;
var init = [];
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// [3,4,5]

var transducer = map(plus2);
var stepper = append;
var init = [];
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// [4,5,6]

唯一改變的是函式帶入map。

那要使用不同的step函式及初始值呢?

var transducer = map(plus1);
var stepper = sum;
var init = 0;
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// 12 (=3+4+5)

var transducer = map(plus2);
var stepper = sum;
var init = 0;
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// 15 (=4+5+6)

var transducer = map(plus1);
var stepper = mult;
var init = 1;
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// 60 (=3*4*5)

var transducer = map(plus2);
var stepper = mult;
var init = 1;
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// 120 (=4*5*6)

這裡我們只更改了stepper及初始值。再一次,我們可以一次計算加總並產生結果而不需要中間聚合。

組成

如果我們想要加3呢?我們可以定義plus3並用map,但我們可以利用轉化者一個特殊屬性的優勢。

結果我們可以就另外兩個函式plus1plus2去定義出plus3

var plus3 = function(item){
  var result = plus2(item);
  result = plus1(result);
  return result;
}

你可能認出這是函式組成。讓我們就組成來說重新定義plus3

function compose2(fn1, fn2){
  return function(item){
    var result = fn2(item);
    result = fn1(result);
    return result;
  }
}

var plus3 = compose2(plus1, plus2);

var output = [plus3(2), plus3(3), plus3(4)];
// [5,6,7]

這裡定義了compose2回傳了兩個韓式的組成結果。你的轉化者函式庫、 Underscore.js或其它函式庫俱有一個組成函式達到相同效果,但其它函式庫還具備了任意數量的函式參數、由右到左順序組成。最後函式呼叫帶上項目引述,接著每一個其他函式順序在右方的會被呼叫,帶上鄰近的計算結果。

讓我們使用compose2來定義一個轉化者,用來將每個項目加3,透過plus1plus2的組成來達成。

var transducerPlus3 = map(compose2(plus1, plus2));
var transducer = transducerPlus3;
var stepper = append;
var init = [];
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// [5,6,7]

我們使用了函式組成來組成傳入到map的現有函式plus1plus2,而非使用新的plus3

為什麼我要告訴你這些?結果是我們也可以透過組成不同轉化者來產生新的轉化者。

var transducerPlus1 = map(plus1);
var transducerPlus2 = map(plus2);
var transducerPlus3 = compose2(transducerPlus1, transducerPlus2);
var transducer = transducerPlus3;
var stepper = append;
var init = [];
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// [5,6,7]

你不需要就此打住,你可以使用新的轉化者再度組成。

var transducerPlus1 = map(plus1);
var transducerPlus2 = map(plus2);
var transducerPlus3 = compose2(transducerPlus1, transducerPlus2);
var transducerPlus4 = compose2(transducerPlus3, transducerPlus1);
var transducer = transducerPlus4;
var stepper = append;
var init = [];
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);

注意,再一次,上面範例中唯一差別在於建立轉化器的那段。其他都是一樣的。

組成能夠運作是因為轉化者被定義成接受轉化器並傳回轉化器。單一引數與回傳值的型別相同。每當這個案例時,你可以使用函式組成來建立新的函式俱有相同的參數型別。

我們證明了轉化者是"可組合的演算轉變"。這在實踐中可以非常強大:你可以定義新的轉化器作為一系列的小型轉化器,並將它們以管線方式組成。我們將在未來文章中有更多的範例。

結果成為儘管函式組成是由右到左,轉化本身過程是由左到右。上述transducerPlus4範例中,每個項目在plus1轉化中已經進行plus3轉化。

儘管在這個範例中順序並不重要,記住由左到右的轉化順序非常重要。這讓你更容易了解轉化過程的順序如同你閱讀程式碼的順序(如果你的語言像是英語)。

結論第一部...

轉化者允許抽象可組成的轉變演算,使其獨立於輸入與輸出,甚至是迭代的過程。

這篇文章中,我們示範了如何使用轉化者來抽象轉化演算成一個轉化者,接受轉化器及傳回轉化器。轉化器可以用在transduce去迭代並轉化輸入來源。

Underscore.jsLo-Dash操作陣列及物件計算中間結果,轉化者定義了轉化器,就函式而言相似於你傳入到reduce:開始於初始值作為初始結果值,執行函式帶入初始結果值以及項目,回傳可能轉化的結果給下一回迭代。一旦你將轉化過程從資料中抽象化,你可以應用相同的轉化過程到不同的處理程序,開始於初始值且步進透過一個結果值。

我們證明相同轉化者可以操作不同輸出來源,透過更改初始值以及你用來產生轉化器的stepper。一個好處是這樣的抽象讓你可以一次傳遞中就計算結果,不需要額外的中間聚合陣列。

儘管,沒有明確地聲明,我們也證明了轉化者解耦迭代及來自轉化者的輸入來源。我們用相同的轉化者,手動迭代每個項目