Transducing

const isOdd = (x) => x % 2 === 1;
const add = (x) => (y) => x + y;

const arr = [1, 2, 3, 4, 5];

arr
  .map(square) // [ 1 → 1, 2 → 4, 3 → 9, 4 → 16, 5 → 25 ]
  .map(add(3)); // [ 1 → 4, 4 → 7, 9 → 12, 16 → 19, 25 → 28 ]

위의 상황에서 코드는 문제없이 동작하지만 많은 요소를 갖는 배열에 대해서는 Array.prototype.map을 호출할 때마다 즉, 메서드 체이닝을 수행할 때마다 원본 배열과 동일한 크기의 중간 배열을 지속적으로 생성한다는 문제가 있다. 또한 이전 메서드의 호출 결과가 반환되기 이전에는 다음 메서드 호출이 수행되지 않으므로 각 메서드의 수행 시간을 모두 합친 만큼의 blocking이 발생하게 될 것이다.

그렇다면 중간 배열을 생성하지 않고, 최종 결과로 반환될 배열만 추가로 생성하게끔 구현하려면 어떻게 해야할까?

첫 번째 아이디어로는 인접한 mapping 함수들을 합성하는 방식을 떠올릴 수 있을 것이다.

arr.map(pipe(square, add(3)));
// [ 1 → 1 → 4, 2 → 4 → 7, 3 → 9 → 12, 4 → 16 → 19, 5 → 25 → 28]

그렇다면 이번에는 Array.prototype.filter를 체이닝하여 사용하는 경우를 살펴보자.

const isLongEnough = (str) => 1 <= str.length;
const isShortEnough = (str) => str.length <= 3;

const strings = ['abc', 'def', 'gh', '', 'ijkl'];

strings
  .filter(isShortEnough) // [ "abc", "def", "gh", "ijkl" ]
  .filter(isLongEnough); // [ "abc", "def", "gh" ]

mapping 함수의 경우와 마찬가지로 중간 배열을 계속해서 생성하므로 앞선 경우처럼 인접한 predicate 함수들을 합성하는 방식을 가장 먼저 시도해 볼 수 있을 것이다.

strings.filter(pipe(isShortEnough, isLongEnough)); // [] (?)

const tap = (fn) => (value) => {
  fn(value);
  return value;
};

strings.filter(
  pipe(isShortEnough, tap(console.log), isLongEnough),
);
// true, true, true, true, false

true.length; // undefined

이 경우 문제는 predicate 함수의 반환 결과는 boolean이라는 것이다. isLongEnough의 시그니처를 살펴보면 string 타입의 값을 인수로 기대하기 때문에 의도대로 동작하지 않게 되는 것이다.

strings
  .map(strUpperCase) // ["ABC", "DEF", "GH", "", "IJKL"]
  .filter(isLongEnough) // ["ABC", "DEF", "GH", "IJKL"]
  .filter(isShortEnough) // ["ABC", "DEF", "GH"]
  .reduce(strConcat, ''); // "ABCDEFGH"

거기에 만약 Array.prototype.reduce도 함께 사용해야 하는 경우라면 predicate 함수가 반환하는 boolean타입의 값은 reducer 함수와 선택적으로 initialValue를 인수로 제공해야 하는 reduce 함수의 시그니처와의 불일치가 발생하게 된다.

Reducers

그렇다면 이제 두 번째로 고려해볼 수 있는 방법은 합성을 수행할 모든 함수를 동일한 형태의 함수(동일한 시그니처를 갖는 함수)로 만드는 것이 될 수 있을 것이다.

먼저 reduce는 요소를 순회하면서 fold를 수행하고 이를 단일 출력 값으로 만들어내게 된다. 이때 fold란 다음과 같이 단일 출력을 생성하는 이진 연산을 의미한다.

foldLeft는 일반적으로 우리가 알고 있는 reduce 연산을 의미하고, foldRight는 reduceRight를 생각하면 된다.

// Sum: (1, 2) => 3
const add = (a, b) => a + b;

// Product: (2, 4) => 8
const multiply = (a, b) => a * b;

// String concatenation: ("abc", "123") => "abc123"
const concatString = (a, b) => a + b;

// Array concatenation: ([1,2], [3,4]) => [1,2,3,4]
const concatArray = (a, b) => [...a, ...b];

따라서 map, filter와 동일하게 동작할 수 있도록 reducer를 구현하고 이를 reduce에 전달하는 방식으로 변경해보자.

const strUpperCase = (str) => str.toUpperCase();

function strConcatReducer(str1, str2) {
  return str1 + str2;
}

function strUpperCaseReducer(list, str) {
  return [...list, strUpperCase(str)];
}

function isLongEnoughReducer(list, str) {
  if (isLongEnough(str)) return [...list, str];
  return list;
}

function isShortEnoughReducer(list, str) {
  if (isShortEnough(str)) return [...list, str];
  return list;
}

strings
  .reduce(strUpperCaseReducer, [])
  .reduce(isLongEnoughReducer, [])
  .reduce(isShortEnoughReducer, [])
  .reduce(strConcatReducer, '');

하지만 여전히 reducer를 합성하는 것에는 문제가 있다. reducer는 두 개의 인수를 전달받고 하나의 값을 반환하기 때문에 이전 reducer의 출력을 다음 reducer의 입력으로 전달하는 것이 불가능하기 때문이다.

f: (a, b) => c;
g:          (a, b) => c;

그 대신 reducer 자체를 전달받아 다시 reducer를 반환하는 형태라면 합성이 가능해질 것이다.

    [ reducer ]      [ reducer ]
f: ((a, b) => c) => ((a, b) => c)     [ reducer ]
g:                  ((a, b) => c) => ((a, b) => c)

앞서 구현한 reducer들을 살펴보면 먼저 mapping 함수 혹은 predicate 함수를 적용하는 부분은 매개변수를 통해 전달받게끔 만드는 것이 가능할 것이다.

function mapReducer(mapperFn) {
  return function reducer(list, val) {
    return [...list, mapperFn(val)];
  };
}

const strUpperCaseReducer = mapReducer(strUpperCase);

function filterReducer(predicateFn) {
  return function reducer(list, val) {
    if (predicateFn(val)) return [...list, val];
    return list;
  };
}

const isLongEnoughReducer = filterReducer(isLongEnough);
const isShortEnoughReducer = filterReducer(isShortEnough);

또한 리스트를 반환하는 부분 역시 매개변수로 추출하는 것이 가능하다.

function listCombine(list, val) {
  return [...list, val];
}

function mapReducer(mapperFn, combineFn) {
  return function reducer(list, val) {
    return combineFn(list, mapperFn(val));
  };
}

function filterReducer(predicateFn, combineFn) {
  return function reducer(list, val) {
    if (predicateFn(val)) return combineFn(list, val);
    return list;
  };
}

const strUpperCaseReducer = mapReducer(
  strUpperCase,
  listCombine,
);

const isLongEnoughReducer = filterReducer(
  isLongEnough,
  listCombine,
);

const isShortEnoughReducer = filterReducer(
  isShortEnough,
  listCombine,
);

마지막으로 currying까지 적용해두자.

const curriedFilterReducer = curry(function filterReducer(
  predicateFn,
  combineFn,
) {
  return function reducer(list, val) {
    if (predicateFn(val)) return combineFn(list, val);
    return list;
  };
});

const curriedMapReducer = curry(function mapReducer(
  mapperFn,
  combineFn,
) {
  return function reducer(list, val) {
    return combineFn(list, mapperFn(val));
  };
});

const strUpperCaseReducer = curriedMapReducer(strUpperCase)(
  listCombine,
);

const isLongEnoughReducer = curriedFilterReducer(
  isLongEnough,
)(listCombine);

const isShortEnoughReducer = curriedFilterReducer(
  isShortEnough,
)(listCombine);

Composing Reducers

새롭게 정의한 reducer들은 모두 listCombine을 마지막 인수로 전달받는다는 공통점이 있다. 따라서 listCombine을 전달하기 이전의 함수들은 미리 합성하는 방법을 생각할 수 있다.

그렇다면 먼저 listCombine을 전달하지 않은 상태의 함수를 생각해보자.

const x = curriedMapReducer(strUpperCase);
// const strToUpperCaseReducer = x(listCombine);

const y = curriedFilterReducer(isLongEnough);
// const isLongEnoughReducer = y(listCombine);

const z = curriedFilterReducer(isShortEnough);
// const isShortEnoughReducer = z(listCombine);

3개의 함수를 합성하기 이전에 우선 2개의 함수를 합성하는 경우를 살펴보자. 먼저 y와 z를 합성하는 경우이다. 이 경우 함수 합성은 y(z)의 형태로 수행될 것이다.

// y(z)
function reducer(list, val) {
  if (isLongEnough(val)) return z(list, val);
  return list;
}

// z
(combineFn) => {
  return function reducer(list, val) {
    if (isShortEnough(val)) return combineFn(list, val);
    return list;
  };
};

z는 하나의 인수(combineFn)만을 기대하는 상황이므로 두 개의 인수(list, val)을 전달하게 되면 인수의 타입과 갯수가 일치하지 않아 제대로 동작하지 않을 것이다.

그렇다면 y(z) 대신 y(z(listCombine))의 형태로 합성한 상황을 살펴보자. 이 경우에는 인수의 갯수가 동일하므로 무리없이 합성이 수행될 것이다.

const shortEnoughReducer = z(listCombine);
const longAndShortEnoughReducer = y(shortEnoughReducer);

// z(listCombine)
function reducer(list, val) {  if (isShortEnough(val)) return listCombine(list, val);
  return list;
}

// y(z(listCombine)
function reducer(list, val) {
  if (isLongEnough(val)) {
    return z(listCombine)(list, val);  }
  return list;
}

longAndShortEnoughReducer([], "1"); // ["1"]
longAndShortEnoughReducer([], "1234"); // []

또한 x(y(z(listCombine)))의 형태는 compose(x, y, z)(listCombine)과 동일하므로 다음과 같이 사용하는 것도 가능할 것이다.

const composition = compose(
  curriedMapReducer(strUpperCase),
  curriedFilterReducer(isLongEnough),
  curriedFilterReducer(isShortEnough),
);

const upperLongAndShortEnoughReducer = composition(
  listCombine,
);

// x(y(z(listCombine)))
function reducer(list, val) {
  return y(z(listCombine))(list, strUpperCase(val));
}

strings.reduce(upperLongAndShortEnoughReducer, []);

이때 composition과 같은 역할을 수행하는 함수를 transducer라 한다. 즉, reducer를 전달받아 다시 reducer를 반환하는 Higher-Order-Reducer의 역할을 수행하게 된다. 따라서 각각의 연산에 대해 하나씩 적용을 완료한 리스트를 반환하는 것(중간 컬렉션 생성)이 아니라 각 요소를 순차적으로 순회하면서 요소 별로 합성된 연산을 수행할 수 있게 되는 것이다.

const transducerMap = curry(function mapReducer(mapperFn, combineFn) {
  return function reducer(list, v) {
    return combineFn(list, mapperFn(v));
  };
});

const transduceFilter = curry(function filterReducer(predicateFn, combineFn) {
  return function reducer(list, v) {
    if (predicateFn(v)) return combineFn(list, v);
    return list;
  };
});

const transducer = compose(
  transduceMap(strUpperCase),
  transduceFilter(isLongEnough),
  transduceFilter(isShortEnough),
);

function transduce(transducer, combineFn, initialValue, list) {
  const reducer = transducer(combineFn);
  return list.reduce(reducer, initialValue);}

transduce(transducer, listCombine, [], strings);
// ["ABC", "DEF", "GH"]
transduce(transducer, strConcat, '', strings);
// "ABCDEFGH"

transducer를 이용하면 중간 컬렉션을 만들지 않고 연산을 수행할 수 있게 되었다. 하지만 조금 아쉬운 부분은 transducing을 수행하면서 원하는 값을 얻거나 혹은 특정 상태가 되었을 때 순회를 중단할 방법이 없다는 것과 배열에 대해서만 적용 가능하다는 점이다. 우선 순회를 중단할 방법을 적용하기 위해서는 각각의 순회가 명확한 기준 혹은 인터페이스를 통해 수행될 수 있어야 할 것이다.

The Transducer Protocol

앞서 transducer는 reducer를 전달받아 reducer를 반환하는 역할을 하는 함수라고 소개하였는데, 이를 보다 정확하게 정의하면 transducer란 transformer를 전달받아 새로운 transformer를 반환하는 함수이다. 그렇다면 먼저 transformer가 무엇인지가 정의되어야 transducer에 대한 정의를 이해할 수 있을 것이다.

const transformer = function (reducer) {
  return {
    init: () => 1,
    step: reducer,
    result: (result) => result,
  };
};

이때 transformer 함수가 반환하는 객체가 바로 transformer이며 이는 세 가지 메서드로 구성된다.

init: 초기 값을 제공하는 함수
step: 이진 연산을 수행하는 reducer
result: 연산이 모두 완료되었을 때의 결과를 반환하는 함수

const sum = (a, b) => a + b;
const multiply = (a, b) => a * b;

const input = [2, 3, 4];

const xfSum = transformer(sum);
input.reduce(xfSum.step, xfSum.init());
// 10 (= 1+2+3+4)

const xfMultiply = transformer(multiply);
input.reduce(xfMultiply.step, xfMultiply.init());
// 24 (= 1*2*3*4)

이때 transformer의 step 메서드를 호출하는 것은 미리 전달해둔 reducer를 호출하는 것과 동일하므로 위의 코드에서 Array.prototype.reduce의 첫 번째 인수로 sum 혹은 multiply를 전달한 것과 동일한 결과를 만들어낸다.

그렇다면 보다 재사용성을 높이기 위해 reduce를 수행하는 함수를 만들어보자.

function reduce(xf, init, input) {
  const result = input.reduce(xf.step, init);
  return xf.result(result);
}

const input = [2, 3, 4];

const xfSum = transformer(sum);
reduce(xfSum, xfSum.init(), input);
// 10 (= 1+2+3+4)

하지만 reduce라는 함수의 의미는 일반적으로 reducer를 첫 번째 인수로 전달하는 것으로 여겨지기 때문에 transformer가 아닌 reducer를 직접 전달했을 때도 내부적으로 transformer로 변환하도록 구현을 약간 수정해보자.

function reduce(xf, init, input) {
  if (typeof xf === 'function') {
    xf = wrap(xf);
  }
  const result = input.reduce(xf.step, init);
  return xf.result(result);
}

function wrap(xf) {
  return {
    // 현재는 init을 인수로 전달받는 형태이므로 초기 값을 반환할 필요가 없다.
    init: () => {
      throw new Error('init does not supported');
    },
    step: xf,
    result: (result) => result,
  };
}

const input = [2, 3, 4];

reduce(sum, 1, input);
// 10 (= 1+2+3+4)

const xfSum = wrap(sum);
reduce(xfSum, 1, input);
// 10 (= 1+2+3+4)

그렇다면 이번에는 리스트의 각 요소에 1을 더한 값들의 합을 구하는 경우를 생각해보자. 어떠한 값에 1을 더한 값을 반환하는 함수를 mapping 함수라 한다면, mapping 함수와 transformer를 전달받아 transformer의 step 메서드가 호출될 때 특정 요소에 mapping 함수가 적용된 결과를 전달하게끔 할 수 있을 것이다.

function mapTransducer(mappingFn) {
  return function transducer(xf) {
    return {
      init() {
        return xf.init();
      },
      step(result, item) {
        return xf.step(result, mappingFn(item));
      },
      result(result) {
        return result;
      },
    };
  };
}

const stepper = wrap(sum);
const init = 0;
const transducer = mapTransducer((item) => item + 1);
const xf = transducer(stepper);

let result = xf.step(init, 2);
// 3 (= sum(0, 2 + 1))

result = xf.step(result, 3);
// 7 (= sum(3, 3 + 1))

result = xf.step(result, 4);
// 12 (= sum(7, 4 + 1))

const output = xf.result(result);
// 12

총합 대신 값이 1씩 증가된 새로운 리스트를 얻고 싶다면 reducer와 초기값만 변경시켜주면 된다.

function append(result, item) {
  result.push(item);
  return result;
}

const stepper = wrap(append);
const init = [];
const transducer = mapTransducer((item) => item + 1);
const xf = transducer(stepper);

let result = xf.step(init, 2);
// [3] (= append([], 2 + 1))

result = xf.step(result, 3);
// [3, 4] (= append([3], 3 + 1))

result = xf.step(result, 4);
// [3, 4, 5] (= append([3, 4], 4 + 1))

const output = xf.result(result);
// [3, 4, 5]

여기서 중요한 점은 wrap에 주입한 reducer가 반환하는 값의 타입과 init의 타입이 동일하다는 사실만 보장된다면 무엇이든 가능하다는 것이다. 또한 transformer의 step 메서드를 이용하여 순회를 진행하기 때문에 프로토콜을 준수하지 않았을 때보다 명확한 인터페이스를 갖게 되었다 할 수 있다.

Transduce

하지만 직접 step을 일일히 제어하는 것은 굉장히 번거로운 작업이기 때문에 이러한 작업을 대신 수행해 줄 별도의 함수로 추출해보자.

function transduce(transducer, stepper, init, input) {
  if (typeof stepper === 'function') {
    stepper = wrap(stepper);
  }

  const xf = transducer(stepper);

  return reduce(xf, init, input);
}

const transducer = mapTransducer((item) => item + 1);
const stepper = append;
const init = [];
const input = [2, 3];
const output = transduce(transducer, stepper, init, input);
// [3, 4]

이제 transduce가 내부적으로 수행하는 동작을 살펴보면 다음과 같다.

          [3] ─────────────╮            [3,4]
           ↑               │              ↑
     append([], 3)         │       append([3], 4)
           ↑               │              ↑
  stepper.step([], 2 + 1)  │   stepper.step([3], 3 + 1)
           ↑               │              ↑
      xf.step([], 2)       │      xf.step([3], 3)
                           ╰───────────────╯

또한 map 이외에도 filter, remove 등의 동작을 수행할 수 있는 transducer를 구현하는 것 역시 크게 어렵지 않다.

function filterTransducer(predicateFn) {
  return function transducer(xf) {
    return {
      init() {
        return xf.init();
      },
      step(result, item) {
        if (predicateFn(item)) {
          return xf.step(result, item);
        }
        return value;
      },
      result(result) {
        return xf.result(result);
      },
    };
  };
}

const not = (predicateFn) => (x) => !predicateFn(x);

function removeTransducer(predicateFn) {
  return filterTransducer(not(predicateFn));
}

맨 앞에서부터 $n$ 개의 요소를 제거하는 drop, 맨 앞에서부터 $n$ 개의 요소를 취하고 나머지는 버리는 take의 경우에는 map, filter 등과 달리 transducer가 반환하는 transformer가 상태를 갖게 된다.

function dropTransducer(n) {
  return function transducer(xf) {
    let left = n;
    return {
      init() {
        return xf.init();
      },
      step(result, item) {
        if (left > 0) {
          left--;
        } else {
          value = xf.step(result, item);
        }
        return value;
      },
      result(result) {
        return xf.result(result);
      },
    };
  };
}

하지만 dropTransducer가 반환하는 transducer 자체는 상태를 갖지 않으므로 transducer 자체는 재사용이 가능하다.

Early Termination

take의 경우는 drop과 반대로 필요한 $n$ 개의 요소를 모두 취했을 때 그 이상의 반복을 중단(early termination)시킬 수 있는 방법이 정의되어야 한다.

function takeTransducer(n) {
  return function transducer(xf) {
    let left = n;
    return {
      init() {
        return xf.init();
      },
      step(result, item) {
        result = xf.step(result, item);
        console.log(result);
        if (--left <= 0) {
          result = reduced(result);
        }
        return result;
      },
      result(result) {
        return xf.result(result);
      },
    };
  };
}

또한 take에서 종료를 알리는 것에서 그치는 것이 아니라 reduce에서 이를 식별하여 반복을 이어나갈 지 혹은 중단할 지에 대해 결정할 수 있어야 한다.

function reduce(xf, init, input) {
  if (typeof xf === 'function') {
    xf = wrap(xf);
  }
  // 종료 여부를 결정할 수 있어야 한다.
  const value = input.reduce(xf.step, init);
  return xf.result(value);
}

현재는 reduce 중간에 개입할 수 있는 방법이 존재하지 않는데다가 배열 이외의 이터러블에 대해서도 적용할 수 있게끔 iterableReduce라는 별도의 함수로 추출해보자.

function reduce(xf, init, input) {
  if (typeof xf === 'function') {
    xf = wrap(xf);
  }
  return iterableReduce(xf, init, input);
}

function iterableReduce(xf, init, input) {
  let value = init;
  for (const item of input) {
    value = xf.step(value, item);
    // value를 통해 종료 여부를 식별할 수 있는 방법이 필요하다.
  }
  return xf.result(value);
}

그렇다면 종료해야 하는 경우 실제 값 이외에도 종료 여부를 식별할 수 있는 값을 갖고 있는 객체를 반환하는 형태를 고려해보자.

function reduced(value) {
  return {
    value,
    reduced: true,
  };
}

function isReduced(value) {
  return value?.reduced;
}

function deref({ value }) {
  return value;
}

이제 iterableReduce와 take에서 모두 이러한 규칙을 지킬 수 있도록 만들어보자. 각 요소를 순회한다는 점은 동일하지만 도중에 reduced라는 상태가 포착된다면 값을 추출하고 그 이상의 순회를 중단하게 된다.

function iterableReduce(xf, init, input) {
  let value = init;
  for (const item of input) {
    value = xf.step(value, item);
    if (isReduced(value)) {
      value = deref(value);
      break;
    }
  }
  return xf.result(value);
}

function takeTransducer(n) {
  return function transducer(xf) {
    let left = n;
    return {
      init() {
        return xf.init();
      },
      step(result, item) {
        result = xf.step(result, item);
        if (--left <= 0) {
          result = reduced(result);
        }
        return result;
      },
      result(result) {
        return xf.result(result);
      },
    };
  };
}

const transducer = takeTransducer(3);
const stepper = append;
const init = [];

const input1 = [1, 2, 3, 4, 5];
const output1 = transduce(
  transducer,
  stepper,
  init,
  input1,
);
// [1, 2, 3]

const input2 = '12345';
const output2 = transduce(
  transducer,
  stepper,
  init,
  input2,
);
// ["1", "2", "3"]

결론

export default function combineReducers(reducers) {
  return function combination(state = {}, action) {
    const newState = {};
    for (const key in reducers) {
      newState[key] = reducers[key](state[key], action);    }
    return newState;
  };
}

redux의 combineReducers가 반환하는 combination 내부를 살펴보면 상태를 변경시키는 모든 연산이 reducer 단위로 이루어지는 것을 확인할 수 있다.
최종적인 연산의 결과는 새로운 객체이지만 갱신을 수행하면서 내부적으로 newState라는 객체를 공유하는 것을 알 수 있다.
즉, Transducing이나 redux에서나 Structural Sharing을 최대한 활용하는 방향으로 갱신을 수행하는 것으로 판단된다.
Transducing을 공부하면서 transformer의 형태가 이터레이터와 매우 유사하다는 사실을 알 수 있었다. step 메서드를 이터레이터의 next 메서드라 생각한다면 이터레이터, 제너레이터, transducer 모두 깊은 연관을 가지는 것이 아닐까 추측된다.

Reducers
Composing Reducers
The Transducer Protocol
Transduce
Early Termination
결론