Recursive Data Structures and Lazy Evaluation

2025.11.14

Roman Liutikov 블로그 포스트 번역

2017년 7월 29일

원문: https://romanliutikov.com/blog/recursive-data-structures-and-lazy-evaluation

이 글에서 저는 재귀적 데이터 구조와 lazy evaluation이 어떻게 함께 작동하는지 스스로 설명해보려고 합니다. 저는 매일 이들을 사용하지만, 기본 구현과 일반적인 개념에 대해 깊이 생각해본 적이 없었습니다.

먼저 문제를 정의하고 재귀적 해결책을 설명합니다. 그 후 간단한 데이터 구조를 재귀적으로 구현해봅니다. 개념을 이해한 후에는 lazy evaluation을 다루고 해당 데이터 구조의 lazy 버전을 제시하겠습니다.

문제

게임 개발의 전형적인 문제는 충돌 감지(collision detection)입니다. 이 기술은 좌표 공간에서 엔티티 간의 교차를 감지하는 데 사용됩니다. 예를 들어 슈팅 게임에서 적과 총알 간의 교차를 감지합니다.

2D 우주 슈팅 게임을 만들고 있다고 상상해봅시다. 이 게임은 적 엔티티와 플레이어의 미사일 간의 상호작용을 포함합니다. 적 엔티티가 파괴되었는지 판단하기 위해 게임은 미사일이 2차원 좌표 공간에서 엔티티와 교차하는 시점을 감지할 수 있어야 합니다. 우리 게임의 충돌 감지 알고리즘은 다음과 같이 설명할 수 있습니다:

현재 화면에 있는 모든 미사일 엔티티의 목록과 모든 적 엔티티의 목록을 작성합니다

목록에서 첫 번째/다음 미사일 엔티티를 가져옵니다

모든 적 엔티티에 대해 위치를 확인합니다

위치가 일치하면 — 충돌이 감지되고, 두 엔티티를 목록에서 제거한 후 2단계부터 반복합니다

그렇지 않으면 — 목록의 끝까지 2단계부터 반복합니다

보시다시피 이 알고리즘은 간단하며 반복을 통해 쉽게 구현할 수 있습니다.

for (let i = 0; i < missiles.length; i++) {
  const missile = missiles[i];
  for (let j = 0; j < enemies.length; j++) {
    const enemy = enemies[j];
    if (missile.intersects(enemy)) {
      // collision is detected
    }
  }
}

그러나 이 단순한 접근 방식의 문제는 O(n*(n-1)) 또는 단순히 O(n^2) 시간이 걸린다는 것입니다. 즉, 엔티티의 수가 두 배가 될 때마다 모든 엔티티 간의 충돌을 감지하는 데 필요한 반복 횟수는 4배 더 커집니다. 3개의 엔티티의 경우 대략 9번의 반복이 필요하고, 30개 엔티티의 경우 900번, 300개 엔티티의 경우 90,000번 등입니다. 단일 확인이 상대적으로 저렴한 작업이고 화면에 많은 엔티티가 없다면 이 접근 방식을 사용해도 괜찮지만, 때로는 그렇지 않은 경우도 있습니다.

해결책

명백한 개선 방법은 주어진 엔티티에 대해서만 가까운 엔티티에 대해 충돌 확인을 수행하고 모든 먼 엔티티를 버리는 것입니다. 화면 영역을 별도의 영역으로 나누어 격자를 형성할 수 있으며, 이제 모든 엔티티에 대해 현재 같은 영역에 있는 다른 엔티티에 대해서만 충돌 확인을 수행할 수 있습니다. 이 기술을 공간 분할(space partitioning)이라고 합니다.

더 정교한 알고리즘은 적응형 격자를 사용하는 것입니다. 여기서 셀은 주어진 셀에 현재 있는 엔티티의 수에 따라 자신을 세분화할 수 있습니다.

재귀적 알고리즘

적응형 격자를 구현하는 알고리즘 중 하나를 quadtree 공간 분할이라고 합니다. Quadtree는 모든 노드가 정확히 4개의 자식 노드를 가지는 데이터 구조입니다. Quadtree는 재귀적입니다. 왜냐하면 자신의 관점에서 정의되기 때문입니다(리프 노드를 제외한 모든 노드는 다른 quadtree를 부분 트리로 가집니다).

게임 캔버스는 이러한 노드들 사이에 나뉠 수 있으며, 각 노드는 해당 노드의 경계로 정의된 화면의 영역을 나타냅니다. 노드는 현재 해당 노드에 해당하는 영역에 있는 엔티티를 보유할 수 있습니다. Quadtree 노드는 보유할 수 있는 최대 엔티티 수(주어진 영역의 최대 엔티티 수)를 설정해야 합니다. 노드의 용량이 가득 차면 노드는 자신을 4개의 자식 노드로 세분화하고 화면의 위치에 따라 엔티티를 자식 노드에 분산시킵니다. 세분화는 무한히 깊을 수 있지만, 보통 최대 레벨 수가 설정됩니다.

이 접근 방식의 이점은 모든 엔티티가 화면 전체에 균등하게 분산된 최선의 경우에 모든 충돌 확인을 수행하는 데 필요한 시간이 세분화의 각 레벨마다 4배 감소한다는 것입니다. 즉, 100개의 엔티티의 경우 세분화 1단계로 10,000 대신 2,500번의 확인을 얻고, 2단계로는 625번의 확인을 얻습니다. 올바르게 적용하면 CPU 부하를 줄일 수 있지만, quadtree 유지 관리도 CPU 사이클과 메모리를 소비한다는 것을 잊지 마세요.

Daniel Shiffman의 "The Nature of Code"를 읽으면서 만든 데모입니다.

방금 배운 것은 게임 개발이 재미있고 알고리즘이 그렇게 어렵지 않다는 것입니다. 하지만 이 섹션에서 가장 중요한 것은 재귀적 데이터 구조가 특정 유형의 문제에 대한 자연스러운 해결책이 될 수 있다는 것을 본 것입니다. 이제 코드를 살펴봅시다.

재귀적 데이터 구조

이 섹션에서 우리는 List 데이터 구조, 정확히는 단일 연결 리스트(singly linked list)를 구축할 것입니다. 리스트는 Lisp 프로그래밍 언어의 초기부터 알려진 함수형 프로그래밍의 기본 데이터 구조입니다. Haskell의 List 데이터 타입 선언을 살펴봅시다.

data List a = Nil | Cons a (List a)

리스트는 Nil(빈 리스트) 또는 Cons(구성)로 값과 다른 리스트입니다. 리스트의 다음 값으로 다른 리스트를 가지는 것이 이 데이터 구조를 재귀적으로 만들거나 자신의 관점에서 정의하게 합니다. 리스트의 마지막 값은 항상 Nil이며, 리스트의 끝에 도달했음을 나타내는 데 사용됩니다. Nil은 또한 빈 리스트로 취급되므로 이 타입은 리스트의 속성을 상속합니다. 더 나은 이해를 위해 3개 항목의 리스트가 의사 코드로 어떻게 작성될 수 있는지 보여드립니다:

[1 [2 [3 nil]]]

여기서 2개 항목의 튜플을 cons(구성) 셀이라고 합니다. cons 셀은 첫 번째 위치의 값(head)과 다른 값에 대한 포인터(tail)로 구성됩니다. 따라서 3개 항목의 리스트는 본질적으로 리스트의 끝을 나타내는 Nil이 있는 3개의 cons 셀 체인입니다. 이는 다음과 같이 시각화할 수도 있습니다:

cons 셀로 구축된 리스트는 리스트의 head와 tail에 상수 시간으로 접근할 수 있다는 흥미로운 속성을 가집니다. 반면에 리스트는 인덱싱된 컬렉션(배열)과 같은 효율적인 임의 접근을 제공하지 않습니다.

이제 리스트의 기본 표현을 알았으므로 우리만의 구현을 만들어봅시다. 먼저 데이터 타입을 정의합니다 — 리스트의 구성 요소입니다. 이들은: List, Cons, Nil입니다. List 타입은 리스트를 구축하는 데 정말 필요하지 않습니다. 왜냐하면 리스트는 단지 끝에 Nil이 있는 cons 셀의 체인이기 때문입니다. 오히려 리스트를 생성하고 조작하기 위한 API를 제공할 수 있는 유용한 추상화입니다.

먼저 Nil 타입을 JavaScript 클래스로 구현하고 클래스의 인스턴스인 nil 변수를 생성하여 리스트의 끝 마커로 사용합니다.

class Nil {
  toString() {
    return "Nil";
  }
}
const nil = new Nil();

다음 타입은 Cons입니다. 이는 head 값과 tail — 다음 값에 대한 참조를 받는 클래스입니다. 우리는 또한 new 키워드 사용을 피하기 위해 헬퍼 정적 메서드 .of를 만듭니다.

class Cons {
  constructor(head, tail = nil) {
    this.head = head;
    this.tail = tail;
  }
  toString() {
    return `Cons(${this.head}, ${this.tail})`;
  }
}
Cons.of = (head, tail) => new Cons(head, tail);

cons 셀만 사용해도 이미 값의 리스트를 만들고 해당 값에 접근할 수 있습니다:

const list = Cons.of(1, Cons.of(2, Cons.of(3, nil)));
console.log(list.head);
console.log(list.tail.toString());
console.log(list.tail.head);
console.log(list.tail.tail.tail.toString());

앞서 언급했듯이 cons 셀은 리스트를 만드는 데 충분하지만, Cons 위에 구축된 리스트 추상화는 리스트를 생성하고 조작하기 위한 API를 제공하여 시간과 코드를 절약할 수 있습니다. 따라서 Cons 위에 List 타입을 구축해봅시다:

class List extends Cons {
  constructor(head, tail) {
    super(head, tail);
  }
  toString() {
    return `List(${this.first()}, ${this.rest()})`;
  }
  first() {
    return this.head;
  }
  rest() {
    return this.tail;
  }
}
List.of = (head, tail) => new List(head, tail);
List.fromValues = (head, ...tail) => {
  if (tail.length > 0) {
    return List.of(head, List.fromValues(...tail));
  } else {
    return List.of(head, nil);
  }
};

우리는 또한 임의의 수의 인수에서 리스트를 만들기 위한 .fromValues 헬퍼를 구현합니다. 이것이 재귀적으로 리스트를 구축하는 방법에 주목하세요.

const list = List.fromValues(1, 2, 3);
console.log(list.toString());

또 다른 유용한 작업은 값의 범위를 생성하는 것입니다. List 클래스 정의에 새로운 정적 메서드를 추가합니다:

List.range = (start, end) => {
  if (start < end) {
    return List.of(start, List.range(start + 1, end));
  } else {
    return nil;
  }
};

take 메서드는 리스트에서 임의의 수의 값을 가져오는 데 사용됩니다.

take(n) {
  if (n > 0) {
    return List.of(this.first(), this.rest().take(n - 1));
  } else {
    return List.of(this.first(), nil);
  }
}

range와 take를 사용한 빠른 테스트

const list = List.range(0, 10);
console.log(list.take(3).toString());

지금까지 우리는 검색과 리스트 생성 작업만 구현했습니다. 리스트에 값을 추가하고 값을 매핑하는 작업도 만들어봅시다: add와 map 메서드입니다.

add 작업은 매우 저렴합니다. 왜냐하면 리스트는 head에 효율적인 추가를 지원하기 때문입니다. head 위치에 값이 있는 새 리스트를 만들고 tail 위치에 대상 리스트를 만들면 됩니다:

add(value) {
  return List.of(value, this);
}

map 작업도 head 위치의 값이 재귀적으로 매퍼 함수에 적용되는 새 리스트를 반환합니다:

map(fn) {
  const first = this.first();
  const rest = this.rest();
  if (rest === nil) {
    return List.of(fn(first), nil);
  } else {
    return List.of(fn(first), rest.map(fn));
  }
}
const list = List.range(1, 4).add(0).map(n => n * n);
console.log(list.toString());

filter와 reduce 같은 작업도 map과 유사하게 구현할 수 있습니다.

이 섹션에서 우리는 List 데이터 구조와 그 재귀적 구현에 대해 배웠습니다. 유사한 추론을 앞서 언급한 quadtree와 다른 모든 데이터 구조를 구축하는 데 적용할 수 있습니다. 나중에 여기서 List의 lazy 버전을 만들 것입니다.

Lazy와 Eager Evaluation

List의 lazy 버전을 구현하기 전에 lazy evaluation이 무엇인지 빠르게 상기해봅시다.

두 가지 평가 전략이 있습니다: eager와 lazy입니다. 간단히 말해 eager는 지금 또는 즉시 실행을 의미하고 lazy는 나중에 또는 결과가 필요할 때까지 실행을 지연시키는 것을 의미합니다. Lazy evaluation은 본질적으로 최적화 기법입니다. 현실의 비유는 웹 페이지에서 이미지를 lazy loading하는 것입니다. 많은 이미지가 있는 웹사이트를 열면 브라우저는 모두 즉시 다운로드하기 시작합니다. 반면에 현재 브라우저 창에 표시되는 이미지만 로드하여 대역폭을 절약할 수 있습니다. fold 아래의 이미지는 페이지가 표시되는 위치로 스크롤될 때까지 로드되지 않아야 합니다. 코드에도 동일하게 적용됩니다: 작업 집합은 결과가 실제로 필요할 때 요청 시 실행됩니다.

Eager evaluation은 더 간단한 의미에서 더 직관적입니다. JavaScript와 Ruby 같은 언어에서 표준 평가 전략입니다. 다음 예를 고려해봅시다(평가 프로세스는 주석에 설명되어 있습니다):

range(0, 10) // [0..9]
  .map((n) => n + 1) // [1..10]
  .filter((n) => n % 2 === 0) // [2 4 6 8 10]
  .take(3); // [2 4 6]

코드가 제자리에서 실행되고 결과가 즉시 반환됨을 알 수 있습니다.

Lazy evaluation 전략은 다릅니다.

range(0, 10) // nothing happened
  .map((n) => n + 1) // nothing happened
  .filter((n) => n % 2 === 0) // nothing happened
  .take(3) // nothing happened
  .run(); // [2 4 6]

체인의 작업 중 어느 것도 .run 메서드 호출까지 실행되지 않습니다. 물론 nothing happened는 완전히 사실이 아닙니다. 호출될 때마다 작업이 나중에 실행되도록 저장되고 결과가 요청되면 전체 체인이 실행되고 최종 값이 반환됩니다. Haskell과 Clojure 같은 언어는 지연된 실행에 크게 의존합니다. Haskell에서는 예를 들어 모든 것이 thunk에 저장됩니다. thunk를 평가를 방지하는 임의의 코드에 대한 컨테이너로 생각할 수 있습니다. 식을 포함하는 클로저일 수 있습니다. Eager 버전의 1 + 1은 JavaScript에서 lazy () => 1 + 1로 표현될 수 있습니다. 예를 들어 숫자를 더하고 빼는 lazy 함수를 만들어봅시다:

const add = (a, b) => {
  return () => {
    a = typeof a === "function" ? a() : a;
    b = typeof b === "function" ? b() : b;
    return a + b;
  };
};
const sub = (a, b) => {
  return () => {
    a = typeof a === "function" ? a() : a;
    b = typeof b === "function" ? b() : b;
    return a - b;
  };
};

add와 sub 모두 인수를 닫은 함수를 반환하므로 실제 작업은 아직 실행되지 않으며, 반환된 thunk를 호출하여 강제할 때까지 실행되지 않습니다.

const thunk = (fn) => {
  fn.toString = () => "[Thunk]";
  return fn;
};
const add = (a, b) => {
  return thunk(() => {
    a = typeof a === "function" ? a() : a;
    b = typeof b === "function" ? b() : b;
    return a + b;
  });
};
const sub = (a, b) => {
  return thunk(() => {
    a = typeof a === "function" ? a() : a;
    b = typeof b === "function" ? b() : b;
    return a - b;
  });
};
const result1 = sub(20, add(10, 5));
const result2 = add(3, sub(5, 7));
const result3 = add(result1, result2);
console.log(result1);
console.log(result2);
console.log(result3);
console.log(result3());

Lazy evaluation은 항상 메모이제이션과 함께 제공되며, 이는 또 다른 최적화입니다. thunk가 평가되면 클로저에서 결과를 캐시할 수 있고 전체를 반복해서 평가하는 대신 후속 호출에서 캐시된 값을 반환합니다. 다음은 이전 예의 수정된 버전입니다:

const memoize = (fn) => {
  let cache;
  return () => {
    if (cache) {
      console.log("Return cached");
      return cache;
    } else {
      console.log("Evaluate");
      cache = fn();
      return cache;
    }
  };
};
const add = (a, b) => {
  return memoize(() => {
    a = typeof a === "function" ? a() : a;
    b = typeof b === "function" ? b() : b;
    return a + b;
  });
};
const sub = (a, b) => {
  return memoize(() => {
    a = typeof a === "function" ? a() : a;
    b = typeof b === "function" ? b() : b;
    return a - b;
  });
};
const result1 = sub(20, add(10, 5));
const result2 = add(3, sub(5, 7));
const result3 = add(result1, result2);
console.log(result3());
console.log(result3());

Lazy와 재귀적 데이터 구조

다음은 Cons 타입 위에 구축할 LazyList 추상화의 초기 구현입니다.

class LazyList {
  constructor(fn) {
    this._fn = fn;
  }
  toString() {
    return `LazyList(${this.next()})`;
  }
  next() {
    return this._fn();
  }
  first() {
    return this.next().head;
  }
  rest() {
    return this.next().tail;
  }
}
LazyList.of = (fn) => new LazyList(fn);

여기서 fn은 cons 셀을 반환해야 하는 thunk이고 next 메서드는 thunk를 평가합니다.

.fromValues 헬퍼가 어떻게 리스트를 lazy하고 재귀적으로 구축하는지 보세요. 이는 인수의 값이 있는 head와 다른 lazy 리스트인 tail을 가진 Cons의 thunk를 포함하는 LazyList의 인스턴스를 반환합니다.

LazyList.fromValues = (head, ...tail) => {
  return LazyList.of(() => {
    if (tail.length > 0) {
      return Cons.of(head, LazyList.fromValues(...tail));
    } else {
      return Cons.of(head, nil);
    }
  });
};
const list = LazyList.fromValues(1, 2, 3);
console.log(list.toString());

take도 lazy 리스트를 반환합니다. 하지만 실제 값을 가져오기 위해 thunk를 하나씩 평가하고 대상 리스트의 tail에서 가져온 후 새로운 것을 구성합니다.

take(n) {
  if (n > 0) {
    return LazyList.of(() => {
      const head = this.first();
      const tail = this.rest();
      if (tail === nil) {
        return Cons.of(head, nil);
      } else {
        return Cons.of(head, tail.take(n - 1));
      }
    });
  }
}

range는 값의 범위를 반환하는데, 이제 laziness를 사용하면 무한 리스트를 만들 수 있습니다.

LazyList.range = (start = 0, end = Infinity) => {
  if (start < end) {
    return LazyList.of(() => Cons.of(start, LazyList.range(start + 1, end)));
  }
};
const list = LazyList.range();
console.log(list.take(2).toString());
console.log(list.take(5).toString());

lazy 리스트에 값을 추가하는 것은 List 구현과 매우 유사합니다.

add(value) {
  return LazyList.of(() => Cons.of(value, this));
}

map 작업도 eager 버전과 유사합니다.

map(fn) {
  return LazyList.of(() => {
    const first = this.first();
    const rest = this.rest();
    return Cons.of(fn(first), rest.map(fn));
  });
}

이제 무한 리스트를 만들고 그 위에 정의된 작업 집합을 만들 수 있습니다.

const list = LazyList.range().map((n) => n * n);
console.log(list.take(2).toString());
console.log(list.take(5).toString());

지금까지 우리는 전체 리스트를 평가하는 하나의 메서드만 가지고 있었습니다: .toString. 일반적인 JavaScript 시설을 사용하여 리스트를 사용할 수 있으려면 의미 있는 것으로 변환되어야 합니다. 예를 들어 배열입니다. .toArray 메서드는 정확히 이것을 합니다.

toArray() {
  const first = this.first();
  const rest = this.rest();
  if (rest === nil) {
    return [first];
  } else {
    return [first, ...rest.toArray()];
  }
}
list.take(5).toArray()

이제 메모이제이션을 추가해봅시다. 누군가 리스트에서 값을 검색하기 위해 .next 메서드를 호출할 때마다 thunk를 평가하고 결과를 메모이제이션하거나 이미 캐시된 경우 결과를 반환합니다. LazyList 클래스에 필요한 수정 사항은 다음과 같습니다:

constructor(fn) {
  this._fn = fn;
  this._next = null; // cache
}
next() {
  // if there's a thunk
  if (typeof this._fn === 'function') {
    this._next = this._fn(); // evaluate it and cache the result
    this._fn = null; // we don't need thunk anymore
    return this._next; // return cached  value
  } else {
    // other just return cached value
    return this._next;
  }
}

데이터베이스에서 사용자 레코드를 lazy하게 가져오는 이 예를 보세요. getUsers 함수는 thunk가 평가될 때 요청 시 데이터베이스에서 사용자 레코드를 가져와 리스트를 lazy하게 생성합니다.

const getUsers = (db, [id, ...ids]) => {
  return LazyList.of(() => {
    if (ids.length > 0) {
      return Cons.of(db.getUserByID(id), getUsers(db, ids));
    } else {
      return Cons.of(db.getUserByID(id), nil);
    }
  });
};
// usage
const ids = db.getUsersIDs();
const users = getUsers(db, ids); // nothing happened
const firstThreeUsers = users.take(3).map(({ id }) => id); // nothing happened
firstThreeUsers.toArray(); // [1, 2, 3]

이를 테스트해봅시다. 아래 코드를 실행하면 첫 번째 실행은 약 1초가 걸리지만 다음 실행은 1ms 미만이 걸립니다. 다른 작업을 실행하더라도 말입니다. 이는 users 리스트가 첫 번째 실행에서 평가되었고 결과가 후속 호출을 위해 메모이제이션되었기 때문입니다.

// benchmark helper
const time = (fn) => {
  const start = performance.now();
  const result = fn();
  const delta = performance.now() - start;
  console.log(Math.round(delta * 100) / 100);
  return result;
};
// db mock
const db = {
  getUsersIDs() {
    return [1, 2, 3, 4, 5, 6];
  },
  getUserByID(id) {
    for (let i = 0; i < 1e8; i++) {}
    return { id };
  }
};
const getUsers = (db, [id, ...ids]) => {
  return LazyList.of(() => {
    if (ids.length > 0) {
      return Cons.of(db.getUserByID(id), getUsers(db, ids));
    } else {
      return Cons.of(db.getUserByID(id), nil);
    }
  });
};
const users = getUsers(db, [1, 2, 3, 4, 5, 6]);
time(() =>
   users
     .take(6)
     .toArray());
time(() =>
  users
    .map(id => 'user id ' + id)
    .take(3)
    .toArray());

이것이 전부입니다 🎬

함수형 데이터 구조 학습에 관심이 있으시다면 Okasaki의 책 "Purely Functional Data Structures"를 읽어보시기를 강력히 권장합니다.

119

아직 댓글이 없습니다.

첫 번째 댓글을 작성해보세요!