Reduce in

Über Reduce

Angenommen, wir möchten ein Array von Zahlen summieren. Es gibt viele Möglichkeiten, dieses Ziel zu erreichen.

• In vielen Sprachen wird dieses Problem als Schleife mit einer Akkumulatorvariablen ausgedrückt.

• Dieses Problem kann als rekursive Funktion geschrieben werden. In Pseudocode könnte das so aussehen.

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

  Diese Methode, das Problem in kleinere Teile zu zerlegen, kann auch als „Reduzieren auf den Basisfall“ beschrieben werden.

Reduce ist eine Möglichkeit, alle Elemente einer Datenstruktur zu einem einzigen Wert zusammenzufassen. Der Prozess iteriert über die Datenstruktur und wendet auf jedes Element eine Funktion an, um das akkumulierte Ergebnis zu aktualisieren.

In jq ist dieser Prozess im reduce-Filter implementiert. In anderen Sprachen wird er manchmal „fold“, „fold-left“, „inject“ oder „aggregate“ genannt.

Der reduce-Ausdruck in jq sieht so aus.

reduce STREAM_EXPRESSION as $var (INITIAL_VALUE; UPDATE_EXPRESSION)

• STREAM_EXPRESSION ist ein Stream von Elementen, die nacheinander in der Variable $var gespeichert werden.
  • Zur Erinnerung: Um ein Array zu streamen, verwende den Iterator-Filter .[]: $myArray | .[].
• INITIAL_VALUE ist der Startwert des akkumulierten Ergebnisses (bekannt als „Akkumulator“).
• Der UPDATE_EXPRESSION kombiniert („faltet“) den aktuellen Wert ($var) in den Akkumulator.
  • Im Kontext dieses Ausdrucks ist . der Wert des Akkumulators.
  • Die Ausgabe des Ausdrucks wird für die nächste Iteration im Akkumulator gespeichert.
  • Nach der letzten Iteration ist das akkumulierte Ergebnis die Ausgabe von reduce.

Schauen wir uns ein Beispiel an: die Zahlen in einem Array addieren. Der add-Filter macht genau das, aber wir werden sehen, wie man ihn implementiert.

Wenn wir [10, 20, 30, 40] als Eingabe verwenden und Null als Anfangszustand nehmen, sieht jeder Schritt so aus.

In der jq-Syntax sieht das so aus.

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

Das können wir mit dem reduce-Filter ausdrücken.

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

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

Ein paar Dinge, die du beachten solltest

• Im reduzierenden Ausdruck ist . der Akkumulator. Wenn die Eingabe ein Objekt ist, auf das du innerhalb der reduzierenden Funktion zugreifen musst, musst du es in einer Variable speichern.

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

• Der Akkumulator kann von jedem Datentyp sein. Zum Beispiel möchtest du vielleicht ein Array umkehren.

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