歸約 在

關於 歸約

假設我們想把一個數字陣列加總起來。要達成這個目標有很多種方法。

• 在許多語言中，這個問題會用帶有累加器變數的迴圈來表達。

• 這個問題也可以寫成遞迴函式。用虛擬碼表示的話，可能會像這樣。

  function Add(X, Sum=0):
    if X is empty then
      return Sum
    else
      return Add(rest(X), Sum + first(X))
    end
  end
  

  這種把問題拆解成更小片段的方法，也可以描述為「逐步 reduce 至基本情況」。

Reduce是一種把資料結構中所有元素合併成單一值的方式。這個過程會疊代資料結構，對每個元素套用函式，藉此更新累積的結果。

在jq中，這個過程是由reduce篩選器實作的。在其他語言裡，它可能叫做「fold」、「fold-left」、「inject」或「aggregate」。

jq的reduce運算式看起來像這樣。

reduce STREAM_EXPRESSION as $var (INITIAL_VALUE; UPDATE_EXPRESSION)

• STREAM_EXPRESSION是一個項目的_串流_，每個項目會依序存入$var變數。
  • 提醒一下，若要將陣列串流化，請使用迭代器篩選器.[]：$myArray | .[]。
• INITIAL_VALUE是累積結果的起始值（稱為「累加器」）。
• UPDATE_EXPRESSION會將當前值（$var）合併（「折疊」）進累加器。
  • 在這個運算式的脈絡下，.就是累加器的值。
  • 運算式的輸出會存入累加器，供下一次疊代使用。
  • 最後一次疊代結束後，累積的結果就是reduce的輸出。

來看一個例子：把陣列中的數字加總。add篩選器就是在做這件事，不過我們來看看怎麼自己實作它。

如果以[10, 20, 30, 40]作為輸入，並以 0 作為初始狀態，每一步會像這樣。

用jq語法寫出來，就像這段程式碼。

0 + 10 | . + 20 | . + 30 | . + 40

我們可以用reduce篩選器來表達這件事。

[10, 20, 30, 40] | reduce .[] as $n (0; . + $n)     # => 100

def add: reduce .[] as $x (null; . + $x);

一些需要注意的事

• 在 reduce 運算式中，.代表累加器。如果輸入是某個物件，而你需要在這段合併函式中引用它，就得把它存進變數。

  {"apple": 10, "banana": 16, "carrot": 4}
  | . as $obj
  | reduce (keys | .[]) as $key (0; . + $obj[$key])     # => 30
  

• 累加器可以是任何資料型態。舉例來說，你可能想反轉一個陣列。

  ["A", "B", "C", "D"]
  | reduce .[] as $elem ([]; [$elem] + .)       # => ["D", "C", "B", "A"]