Statistiques de notes

Reduce

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

• Dans de nombreux langages, ce problème s'exprime sous la forme d'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, qui consiste à diviser le problème en plus petits morceaux, peut aussi se décrire comme le fait de « 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 pour mettre à jour le résultat accumulé.

Dans 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 stream d'éléments, chacun stocké tour à tour dans la variable $var.
  • Pour rappel, pour créer un stream à partir d'un tableau, utilise le filtre itérateur .[] : $myArray | .[].
• INITIAL_VALUE est la valeur de départ du résultat accumulé (appelé « accumulateur »).
• L'UPDATE_EXPRESSION combine (« fold ») la valeur courante ($var) dans l'accumulateur.
  • Dans le contexte de cette expression, . est la valeur de l'accumulateur.
  • Le résultat de l'expression est stocké dans l'accumulateur pour être utilisé à 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"]