핑거 트리: 단순하고 범용적인 자료 구조

Ralf Hinze와 Ross Paterson, Journal of Functional Programming 16(2):197–217, 2006. doi: 10.1017/S0956796805005769

원문 요약의 내용을 한국어로 정리·번역한 것이다.

---

요약

우리는 2-3 핑거 트리(finger tree)를 제시한다. 이는 영속(persistent) 시퀀스의 함수형 표현으로, 양 끝 단에서의 접근을 상각적(amortized) 상수 시간에 지원하고, 연결(concatenation) 및 분할(split) 을 더 작은 쪽 조각의 크기에 대한 로그 시간에 수행한다. 이러한 시간 복잡도를 달성하는 표현은 이미 존재하지만, 2-3 핑거 트리는 그에 비해 구조도, 연산도 훨씬 단순하다. 더 나아가, 분할 연산을 보다 일반적인 형태로 정의함으로써, 이 구조는 시퀀스(sequence), 우선순위 큐(priority queue), 탐색 트리(search tree), priority search queue 등으로 사용할 수 있는 범용 자료 구조가 된다.

기본 구조는 비정규(non-regular) 혹은 중첩(nested) 타입으로 표현된다.

haskell
data FingerTree a = Empty
                  | Single a
                  | Deep (Digit a) (FingerTree (Node a)) (Digit a)

data Digit a = One a | Two a a | Three a a a | Four a a a a

data Node a = Node2 a a | Node3 a a a

이 정의는 2-3 트리의 트리를 만들어 내며, 양 끝에 손가락(finger) 이 두어져 있는 형태로 끝에서의 접근에 유리하다. 예를 들어 다음과 같은 모양이다.

(더 많은 예시)

이 구조는 효율적인 연결도 지원한다. 또한 분할과 탐색을 지원하기 위해, 트리의 내부 노드에 응용별 모노이드(monoid) 로부터 값을 주석(annotate)한다.

• PDF, gzipped PostScript, BibTeX
• 논문 4.2절에서 논의된 응용을 기반으로 한 시퀀스 구현이 모듈 Data.Sequence로 글래스고 Haskell 컴파일러(GHC) 및 다른 Haskell 구현에 포함되어 있다.
  • 참고: 논문에서의 클래스 Reduce는 Haskell 기본 라이브러리의 클래스 Foldable로 대체되었다.
• fingertree 패키지는 다양한 컨테이너 타입의 기반으로 사용할 수 있는 일반적인 핑거 트리 구조를 제공한다.

---

정오표(수정 사항)

4.3절에서 우리는 3절의 연산들을, 생성자를 그에 상응하는 스마트 생성자(smart constructor)로 치환함으로써 측정(measured) 트리로 확장할 수 있다고 제안했다. 그러나 재귀 호출의 결과에 스마트 생성자 deep을 적용하면, 그 재귀 호출을 강제 평가하게 되고, 이는 분석에 결정적인 역할을 하는 지연성(laziness) 을 잃게 만든다. 대신, 재귀 호출을 강제하지 않고 새로운 측정값(measure)을 계산해야 한다.

• <|의 경우, 마지막 두 절은 다음과 같이 쓸 수 있다.

  haskell
  a <| Deep v [b, c, d, e] m sf =
    Deep (|a| + v) [a, b] (node3 c d e <| m) sf
  
  a <| Deep v pr m sf =
    Deep (|a| + v) ([a] ++ pr) m sf

• deepL의 경우, 첫 번째 절은 다음과 같이 쓸 수 있다.

  haskell
  deepL [] m sf = case viewL m of
                    NilL       -> toTree sf
                    ConsL a m' -> Deep (|m| + |sf|) (toList a) m' sf

---

함께 보면 좋은 자료

• Chris Okasaki. Purely Functional Data Structures, Cambridge University Press, 1998.

  함수형 자료 구조를 설계하기 위한 일반적인 기법들을 다양한 응용과 함께 제시하는 훌륭한 책이다. 핑거 트리는 이 책의 11.1절에서 논의되는 암시적 덱(implicit deque) 의 확장으로 볼 수 있다.

  haskell
  data ImplicitDeque a = Empty
                       | Single a
                       | Deep (Digit a) (ImplicitDeque (a, a)) (Digit a)
  
  data Digit a = One a | Two a a | Three a a a

  핑거 트리는 이 구조에 다음 두 가지 확장을 적용한 결과이다.

  1. 쌍(pair)을 2-3 노드로 대체하여, 효율적인 연결을 지원할 수 있을 만큼의 유연성을 확보한다. (덱 연산의 상수 시간 보장을 유지하려면 Digit을 Four까지 확장해야 한다.)
  2. 내부 노드에 모노이드를 주석으로 붙이면, 효율적인 분할을 지원할 수 있다.

  이 책은 Okasaki의 박사 학위 논문을 확장한 것으로, 암시적 덱은 논문 8.4절에서 논의된다.

• Koen Claessen. "Finger trees explained anew, and slightly simplified (functional pearl)", Haskell 2020 (PDF).

  1에서 3까지 크기의 digit을 사용하는 변형을 제시한다.

• 연결 가능한 영속 덱(catenable persistent deque)의 다른 구현:

  • H. Kaplan, R. E. Tarjan. "Purely functional representations of catenable sorted lists", Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 202–211, ACM Press, 1996.

    동일한 시간 복잡도를, 상각이 아니라 최악의 경우(worst case) 에도 보장하는 보다 복잡한 구조를 제안한다. 또한, 연결을 이중 로그 시간에 수행한다고 주장되는 변형을 개략적으로 소개한다.

  • H. Kaplan, R. E. Tarjan. "Purely Functional, Real-Time Deques with Catenation", Journal of the ACM (JACM), 46(5):577–603, 1999.

    위 구조를 정교화하여, 최악의 경우에도 실시간(real-time) 상수 시간 덱 연산과 연결을 제공한다.

  • Radu Mihaesau와 Robert Tarjan의 추가적인 개선 (2003).

• 블로그에 실린 핑거 트리 튜토리얼들:

  • apfelmus
  • Edward Kmett
  • Tommy McGuire
  • Andrew Gibiansky

• 다른 언어로의 구현:

  • C#
  • Clojure
  • Coq
  • Humus
  • Java
  • Scala
  • Isabelle/HOL