Purely Functional Data Structures

基本信息

Paperback: 232页

出版社: Cambridge University Press (1999年6月13日)

语种： English

ISBN-10: 0521663504

ISBN-13: 978-0521663502

产品尺寸及重量: 153 x 227 x 18mm | 350g

书籍简介

Most books on data structures assume an imperative language such as C or C++. However, data structures for these languages do not always translate well to functional languages such as Standard ML, Haskell, or Scheme. This book describes data structures from the point of view of functional languages, with examples, and presents design techniques that allow programmers to develop their own functional data structures. The author includes both classical data structures, such as red-black trees and binomial queues, and a host of new data structures developed exclusively for functional languages. All source code is given in Standard ML and Haskell, and most of the programs are easily adaptable to other functional languages. This handy reference for professional programmers working with functional languages can also be used as a tutorial or for self-study.

Stresses techniques of data structure design rather than just finished products

Source code in Standard ML and in Haskell, easily adaptable to other functional languages

For professional programmers working with functional languages: can also be used as a tutorial or for self-study

目录

1. Introduction

2. Persistence

3. Some familiar data structures in a functional setting

4. Lazy evaluation

5. Fundamentals of amortization

6. Amortization and persistence via lazy evaluation

7. Eliminating amortization

8. Lazy rebuilding

9. Numerical representations

10. Data-structural bootstrapping

11. Implicit recursive slowdown

Appendix: Haskell source code.

作者简介

Chris Okasaki, Columbia University, New York

Chris Okasaki, Ph.D. is an associate professor of computer science at the United States Military Academy. He authored Purely Functional Data Structures (1998), based on a doctoral dissertation of the same name. He obtained a Ph.D. at Carnegie Mellon University in 1996 under advisers Peter Lee, Robert Harper, Daniel Sleator, and Robert Tarjan.[1] Prior to his current academic appointment, he taught at Columbia University and the University of Glasgow.