순수 함수형 데이터 구조(양장본 Hardcover)

★ 이 책의 구성과 대상 독자 ★

데이터 구조를 다루는 대부분의 책에서는 C나 C++와 같은 명령형(imperative) 언어를 가정하고 설명한다. 하지만 명령형 언어의 데이터 구조는 SML(Standard ML), 하스켈(Haskell), 스킴(Scheme) 등의 함수형 언어로 잘 변환되기 어렵다. 이 책은 함수형 언어의 관점에서 데이터 구조를 살펴보고, 프로그래머가 자신만의 함수형 데이터 구조를 개발할 때 도움이 되는 여러 설계 기법을 보여준다. 적흑 트리(red-black tree)나 이항 큐(binomial queue) 등의 전통적인 데이터 구조를 배우며, 함수형 언어를 위해 별도로 개발한 여러 데이터 구조를 살펴본다. 모든 소스 코드는 SML과 하스켈로 만들어졌지만, 그 밖의 함수형 언어로도 쉽게 바꿀 수 있을 것이다.

이 책은 함수형 언어를 다루는 전문 프로그래머가 간편하게 참고할 수 있는 책이며, 함수형 언어를 공부하고 싶은 개발자에게는 자습서로 쓰기 좋다.

1장. 소개

1.1 함수형 데이터 구조와 명령형 데이터 구조 비교

1.2 미리 계산하는 언어와 지연 계산 언어

1.3 용어

1.4 접근 방법

1.5 이 책의 개요



2장. 영속성

2.1 리스트

2.2 이진 검색 트리

2.3 참고사항



3장. 이미 잘 알려져 있는 데이터 구조의 함수형 구현

3.1 레프티스트 힙

3.2 이항 힙

3.3 적흑 트리

3.4 참고사항



4장. 지연 계산

4.1 $ 표기법

4.2 스트림

4.3 참고사항



5장. 분할 상환 기초

5.1 분할 상환 분석 기법들

5.2 큐

5.3 이항 힙

5.4 스플레이 힙

5.5 페어링 힙

5.6 나쁜 소식

5.7 참고사항



6장. 지연 계산을 통해 분할 상환과 영속성을 동시에 달성하기

6.1 실행 트레이스와 논리적 시간

6.2 영속성과 분할 상환 사이를 중재하기

6.2.1 지연 계산의 역할

6.2.2 지연 계산 데이터 구조를 분석하기 위한 프레임워크

6.3 은행원 기법

6.3.1 은행원 기법의 정당성

6.3.2 예제: 큐

6.3.3 부채 상속

6.4 물리학자 기법

6.4.1 예제: 이항 힙

6.4.2 예제: 큐

6.4.3 예제: 공유를 사용하는 상향식 병합 정렬

6.5 지연 계산 페어링 힙

6.6 참고사항



7장. 분할 상환 없애기

7.1 스케줄링

7.2 실시간 질의

7.3 이항 힙

7.4 공유를 사용한 상향식 병합 정렬

7.5 참고사항



8장. 지연 재구축

8.1 일괄 재구축

8.2 전역 재구축

8.2.1 예제: 후드-멜빌 실시간 큐

8.3 지연 재구축

8.4 양방향 큐

8.4.1 출력이 제한된 데크

8.4.2 은행원의 데크

8.4.3 실시간 데크

8.5 참고사항



9장. 수치적 표현

9.1 위치에 기반한 수 체계

9.2 이진수

9.2.1 이진 임의 접근 리스트

9.2.2 영이 없는 표현들.

9.2.3 지연 계산 표현

9.2.4 조각을 사용하는 표현

9.3 치우친 이진수

9.3.1 치우친 이진 임의 접근 리스트

9.3.2 치우친 이항 힙.

9.4 삼진수와 사진수

9.5 참고사항



10장. 데이터 구조적 부트스트래핑

10.1 구조적 분해

10.1.1 비균일 재귀와 SML

10.1.2 이진 임의 접근 리스트 다시 보기

10.1.3 부트스트랩으로 만든 큐

10.2 구조적 추상화

10.2.1 효율적 연결을 지원하는 리스트

10.2.2 효율적인 병합을 지원하는 힙

10.3 조합된 타입 부트스트래핑하기

10.3.1 트라이

10.3.2 일반화한 트라이

10.4 참고사항

11 암시적이며 재귀적인 감속

11.1 큐와 데크

11.2 연결 가능한 데크

11.3 참고사항



부록 A. 하스켈 소스 코드

크리스 오카사키 미국 육군사관학교(United States Military Academy)에서 컴퓨터 과학의 부교수로 있으며, 이전에는 콜롬비아 대학교(Columbia University)와 글래스고 대학교(University of Glasgow)에서도 학생들을 가르쳤다.