Réduction en

À propos de Réduction

Supposons que l'on veuille additionner un tableau de nombres. Il existe de nombreuses façons d'atteindre cet objectif.

• Dans de nombreux langages, ce problème s'exprime par une boucle avec une variable d'accumulation.

• Ce problème peut s'écrire sous la forme d'une fonction récursive. En pseudo-code, on pourrait avoir ceci.

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

  Cette méthode de découpage du problème en morceaux plus petits peut aussi se décrire comme « réduire vers le cas de base ».

Reduce est une façon de combiner tous les éléments d'une structure de données en une seule valeur. Le processus parcourt la structure de données en appliquant une fonction à chaque élément afin de mettre à jour le résultat accumulé.

En jq, ce processus est implémenté par le filtre reduce. Dans d'autres langages, on l'appelle parfois « fold », « fold-left », « inject » ou « aggregate ».

L'expression reduce de jq ressemble à ceci.

reduce STREAM_EXPRESSION as $var (INITIAL_VALUE; UPDATE_EXPRESSION)

• STREAM_EXPRESSION est un flux d'éléments, chacun stocké tour à tour dans la variable $var.
  • Rappel : pour transformer un tableau en flux, utilise le filtre d'itération .[] : $myArray | .[].
• INITIAL_VALUE est la valeur de départ du résultat accumulé (que l'on appelle l'« accumulateur »).
• UPDATE_EXPRESSION combine (« replie ») la valeur courante ($var) dans l'accumulateur.
  • Dans le contexte de cette expression, . est la valeur de l'accumulateur.
  • La sortie de l'expression est stockée dans l'accumulateur pour servir à l'itération suivante.
  • Après la dernière itération, le résultat accumulé est la sortie de reduce.

Prenons un exemple : additionner les nombres d'un tableau. Le filtre add fait exactement cela, mais on va voir comment l'implémenter.

Si on utilise [10, 20, 30, 40] comme entrée et zéro comme état initial, voici à quoi ressemble chaque étape.

En syntaxe jq, cela ressemble à ce code.

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

On peut exprimer cela avec le filtre reduce.

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

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

Quelques points à garder en tête

• Dans l'expression de réduction, . est l'accumulateur. Si l'entrée est un objet auquel tu dois faire référence à l'intérieur de la fonction de réduction, tu dois le stocker dans une variable.

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

• L'accumulateur peut être de n'importe quel type de données. Par exemple, tu peux vouloir inverser un tableau.

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