reduce の

reduceについて

数値の配列を合計したいとします。この目的を達成する方法はたくさんあります。

• 多くの言語では、この問題はアキュムレーター変数を使ったループとして表現されます。

• この問題は再帰関数として書くこともできます。擬似コードでは、次のようになるでしょう。

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

  このように問題を小さな部分に分割していく方法は、「ベースケースに向かって畳み込んでいく」と表現することもできます。

Reduceは、データ構造のすべての要素を1つの値にまとめる方法です。この処理では、データ構造を繰り返し処理しながら、各要素に関数を適用して、蓄積された結果を更新していきます。

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

いくつか覚えておきたいこと

• 更新式の中では、.はアキュムレーターです。入力がオブジェクトで、それを更新関数の中から参照する必要がある場合は、いったん変数に格納する必要があります。

  {"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"]