没有合适的资源?快使用搜索试试~ 我知道了~
首页Purely Functional Data Structures (Chris Okasaki)
Purely Functional Data Structures (Chris Okasaki)
![](https://csdnimg.cn/release/wenkucmsfe/public/img/star.98a08eaa.png)
对于 函数编程深入了解的人非常有用。 Okasaki 编写,函数编程 唯一的一本讲述数据结构的书籍
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/5446383/bg1.jpg)
Purely Functional Data Structures
Chris Okasaki
September 1996
CMU-CS-96-177
School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213
Submitted in partial fulfillment of the requirements
for the degree of Doctor of Philosophy.
Thesis Committee:
Peter Lee, Chair
Robert Harper
Daniel Sleator
Robert Tarjan, Princeton University
Copyright
c
1996 Chris Okasaki
This research was sponsored by the Advanced Research Projects Agency (ARPA) under Contract No. F19628-
95-C-0050.
The views and conclusions contained in this document are those of the author and should not be interpreted as
representing the official policies, either expressed or implied, of ARPA or the U.S. Government.
![](https://csdnimg.cn/release/download_crawler_static/5446383/bg2.jpg)
Keywords: functional programming, data structures, lazy evaluation, amortization
![](https://csdnimg.cn/release/download_crawler_static/5446383/bg3.jpg)
For Maria
![](https://csdnimg.cn/release/download_crawler_static/5446383/bg4.jpg)
![](https://csdnimg.cn/release/download_crawler_static/5446383/bg5.jpg)
Abstract
When a C programmer needs an efficient data structure for a particular prob-
lem, he or she can often simply look one up in any of a number of good text-
books or handbooks. Unfortunately, programmers in functional languages such
as Standard ML or Haskell do not have this luxury. Although some data struc-
tures designed for imperative languages such as C can be quite easily adapted to a
functional setting, most cannot, usually because they depend in crucial ways on as-
signments, which are disallowed, or at least discouraged, in functional languages.
To address this imbalance, we describe several techniques for designing functional
data structures, and numerous original data structures based on these techniques,
including multiple variations of lists, queues, double-ended queues, and heaps,
many supporting more exotic features such as random access or efficient catena-
tion.
In addition, we expose the fundamental role of lazy evaluation in amortized
functional data structures. Traditional methods of amortization break down when
old versions of a data structure, not just the most recent, are available for further
processing. This property is known as persistence, and is taken for granted in
functional languages. On the surface, persistence and amortization appear to be
incompatible, but we show how lazy evaluation can be used to resolve this conflict,
yielding amortized data structures that are efficient even when used persistently.
Turning this relationship between lazy evaluation and amortization around, the
notion of amortization also provides the first practical techniques for analyzing the
time requirements of non-trivial lazy programs.
Finally, our data structures offer numerous hints to programming language de-
signers, illustrating the utility of combining strict and lazy evaluation in a single
language, and providing non-trivial examples using polymorphic recursion and
higher-order, recursive modules.
剩余161页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)