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 - це спосіб поєднати всі елементи структури даних в одне значення. Цей процес перебирає структуру даних, застосовуючи функцію до кожного елемента, щоб оновити накопичений результат.

У jq цей процес реалізовано у фільтрі reduce. В інших мовах його можуть називати «fold», «fold-left», «inject» або «aggregate».

Вираз reduce у jq має такий вигляд.

reduce STREAM_EXPRESSION as $var (INITIAL_VALUE; UPDATE_EXPRESSION)

• STREAM_EXPRESSION - це потік елементів, кожен з яких по черзі зберігається у змінній $var.
  • Нагадаємо: щоб отримати потік з масиву, скористайтеся фільтром-ітератором .[]: $myArray | .[].
• INITIAL_VALUE - це початкове значення накопиченого результату (який називають «акумулятором»).
• UPDATE_EXPRESSION поєднує («згортає») поточне значення ($var) в акумулятор.
  • У контексті цього виразу . - це значення акумулятора.
  • Вихідні дані виразу зберігаються в акумуляторі для використання в наступній ітерації.
  • Після останньої ітерації накопичений результат стає вихідними даними reduce.

Розгляньмо приклад: додавання чисел у масиві. Фільтр add робить саме це, але ми побачимо, як його реалізувати.

Якщо взяти [10, 20, 30, 40] як вхідні дані та нуль як початковий стан, ось що відбувається на кожному кроці.

У синтаксисі 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"]