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"라고 부르기도 해요.

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