[functional-js] 지연평가1

이 글은 유인동님의 함수형 프로그래밍 강의내용을 정리한 글입니다.

지연 평가 (Lazy Evaluation)

느긋한 연산(지연 평가)은 계산의 결과 값이 필요할 때 까지 계산을 늦추는 기법이다. 필요할 때까지 계산을 늦추어 불필요한 계산을 줄일수 있다.

지연평가의 이점

1. 불필요한 계산을 하지 않으므로 빠른 계산이 가능하다.
2. 무한 자료 혹은 큰 범위의 자료 구조를 부담없이 사용할 수 있다.
3. 복작합 수식에서 오류를 피할 수 있다.

제너레이터와 이터러블 프로토콜을 따르는 함수들과 함께 사용하면 지연평가를 구현할 수 있다.

range

지정한 범위만큼 배열을 생성하는 함수

const range = length => {
  let i = -1;
  let res = [];
  while (++i < length) {
    res.push(i);
  }
  return res;
};

var list = range(4);
console.log(list); // [0, 1, 2, 3], 값이 생성되었다.
console.log(reduce(add, list)); // 6

L.range

제너레이터를 활용하여 range함수 구현

const L = {};

L.range = function* (length) {
  let i = -1;
  while (++i < length) {
    yield i;
  }
};

var list = L.range(4);
console.log(list); // L.range {<suspended>}, 값이 생성되지 않았다.
console.log(reduce(add, list)); // 6 <- 순회 평가가 발생할 때 동적으로 값이 생성된다.

제너레이터를 활용하면 지연 평가되는 range를 구현할 수 있다.

지정한 범위만큼 배열을 미리 생성하지 않고, 평가할 때 동적으로 생성하는 함수이다.

실제로 순회가 발생하는 평가가 실행될 때 동적으로 값을 생성한다.

take

이터러블에서 limit개수만큼 뽑아내어 배열로 반환하는 함수

const take = (limit, iter) => {
  let res = [];
  for (const a of iter) {
    res.push(a);
    if (res.length == limit) return res;
  }
  return res;
};

// range
console.time('');
console.log(take(5, range(100000))); // [0, 1, 2, 3, 4]
console.timeEnd('');
// 4.06982421875 ms

//L.range
console.time('');
console.log(take(5, L.range(100000))); // [0, 1, 2, 3, 4]
console.timeEnd('');
// 0.299072265625 ms

range 같은 경우 100000의 배열을 만든 후 5개를 출력하지만, L.range 는 미리 배열을 만들지 않고, 필요한 5개의 값만 만든다.

또한 range 같은 겨우 infinity 값을 인자로 사용할 수 없지만, L.range 는 인자로 infinity 값을 집어 넣어 사용할 수 있다.

지연성을 가진 함수로 구현

L.map

L.map = curry(function* (f, iter) {
  for (const a of iter) yield f(a);
});

var it = L.map(a => a + 10, [1, 2, 3]); // 이 때 까지는 값이 생성이 안되어 있다.

// 순회평가가 발생할 때 값이 생성된다.
console.log(it.next()); // {value: 11, done: false}
console.log(it.next()); // {value: 12, done: false}
console.log(it.next()); // {value: 13, done: false}

L.map은 새로운 Array를 만들지 않고, 이터러블을 순회하면서, 각 요소에 대해 함수를 적용한 값을 yield를 통해 게으른 평가를 수행한다.

L.filter

L.filter = curry(function* (f, iter) {
  for (const a of iter) if (f(a)) yield a;
});

var it = L.filter(a => a % 2, [1, 2, 3, 4]);
console.log(it.next()); // {value: 1, done: false}
console.log(it.next()); // {value: 3, done: false}

L.map과 거의 유사한데, 이터러블을 순회하면서, 조건결과 값이 참인 경우에만 값을 yield를 통해 발생한다.

참고

https://opentogether.tistory.com/72

https://kjwsx23.tistory.com/292

엄격한 평가와 지연 평가의 평가 순서

지연 평가는 필요한 정보만 평가하므로, 일반적인 엄격한 평가보다 훨씬 빠른 것을 나타냄을 보여줄 수 있는데 아래 예시를 통해서 각각의 평가의 순서를 알아보자.

// 엄격한 평가
go(range(10),
    map(n => n + 10),
    filter(n => n % 2),
    take(2),
	console.log
);

// 지연 평가
go(L.range(10),
    L.map(n => n + 10),
    L.filter(n => n % 2),
    take(2),
    console.log
);

엄격한 평가

range 에서 0부터 9를 담은 배열을 먼저 생성한 후에, 그 생성한 배열을 map 으로 넘기고, 그 결과 배열을 다시 filter 로 넘기고, 다시 take 로 넘기 면서 순차적으로 평가된다.

순서는 아래와 같다.

지연 평가

지연 평가 함수인 L.range , L.map , L.filter 함수들은 이터레이터를 생성한 후 대기를 한다. 제일 먼저 take 함수가 실행되면서 L.filter 에게 값을 하나 요청한다. L.filter 는 다시 L.map 에게 값을 하나 요청하고 L.map 은 다시 L.range 에게 값을 하나 요청한다.

즉, take -> L.filter -> L.map -> L.range 순으로 실행이 된다.

L.range 에서 0을 생성한 후, L.map 에서 이 요소에 10을 더한 후, L.filter 가 그 값을 판별해 false 되어 더이상 go함수를 진행하지 않고, 다시 L.range 에서 1을 생성하는 식으로 반복한다.

순서는 아래와 같다.

엄격한 평가에서는 range에서 인자로 넣은 값만큼 map 에서 전부 배열을 생성한 후, 이어서 모든 함수를 거쳐가는 반면에, 지연 평가에서는 당장 조건에 해당하는 값을, 동적으로 평가하여 그때 마다 필요로 하는 값을 평가한다.

map, filter 계열 함수들의 결합 법칙

위의 예제를 보았듯이 map, filter 와 같은 함수들이 순차적으로 실행되어 나온 결과 값과 L.map, L.filter 와 같은 함수들이 순차적으로 실행되어 나온 결과 값이 같은 것을 알 수 있다.

이처럼

사용하는 데이터가 무엇이든지, 사용하는 보조 함수(콜백 함수)가 순수 함수(단순 연산 함수)라면 아래 처럼 결합법칙이 성립한다.

예를 들어 0부터 9까지의 값에 map을 우선 다 적용한 뒤 filter를 적용한 결과나, 0부터 하나씩 map과 filter를 차례대로 9까지 적용한 결과가 같다.

(이미지 출처: https://opentogether.tistory.com/72)