순수 함수형 데이터 구조 (불변성과 지연 계산을 활용한 함수형 데이터 구조 | 양장본 Hardcover)

크리스오카사키

미국육군사관학교(UnitedStatesMilitaryAcademy)에서컴퓨터과학의부교수로있으며,이전에는콜롬비아대학교(ColumbiaUniversity)와글래스고대학교(UniversityofGlasgow)에서도학생들을가르쳤다.

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.하스켈소스코드

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