函数式编程数据结构详解：标准ML与Haskell示例

需积分: 9 90 浏览量更新于2024-07-19 1 收藏 5.54MB PDF 举报

"《纯粹函数式数据结构》是一本专为函数式编程语言如Standard ML、Haskell和Scheme设计的数据结构指南。与大多数专注于命令式语言如C++或Java的传统书籍不同，本书侧重于从函数式编程的角度来介绍和探讨数据结构，提供了丰富的示例和设计技巧，帮助程序员在这些语言环境中构建高效、纯函数式的数据结构。书中不仅涵盖了经典的结构，如红黑树和二项队列，还特别介绍了专为函数式编程而设计的独特数据结构。作者克里斯·奥卡西基于哥伦比亚大学的研究，提供所有源代码以Standard ML和Haskell的形式展示，这些代码通常可以轻松地移植到其他函数式语言中，如Lisp或OCaml。作为专业程序员在使用函数式语言时的实用参考书，这本书不仅适合用于实践中的问题解决，也适合作为自我学习的教程。通过阅读这本书，读者不仅能掌握如何在函数式语言中实现高效的数据结构，还能理解其背后的理论基础，如不可变性、无副作用和引用透明性等核心概念，这对于提升编程技能和理解现代软件工程实践至关重要。此外，书中可能还会讨论如惰性求值、元组化和抽象数据类型（ADT）等高级技术，帮助读者在构建函数式应用程序时更加得心应手。"

1.5 Overview 5

• Chapter 6 describes the mediating role lazy evaluation plays in combin-

ing amortization and persistence, and gives two methods for analyzing

the amortized cost of data structures implemented with lazy evaluation.

• Chapter 7 illustrates the power of combining strict and lazy evaluation

in a single language. It describes how one can often derive a worst-

case data structure from an amortized data structure by systematically

scheduling the premature execution of lazy components.

The third part of the book (Chapters 8-11) explores a handful of general tech-

niques for designing functional data structures.

• Chapter 8 describes lazy rebuilding, a lazy variant of global

rebuild-

ing [Ove83]. Lazy rebuilding is significantly simpler than global rebuild-

ing, but yields amortized rather than worst-case bounds. Combining lazy

rebuilding with the scheduling techniques of Chapter 7 often restores the

worst-case bounds.

• Chapter 9 explores numerical representations, which are implementa-

tions designed in analogy to representations of numbers (typically bi-

nary numbers). In this model, designing efficient insertion and deletion

routines corresponds to choosing variants of binary numbers in which

adding or subtracting one take constant time.

• Chapter 10 examines data-structural bootstrapping [Buc93]. This tech-

nique comes in three flavors: structural decomposition, in which un-

bounded solutions are bootstrapped from bounded solutions; structural

abstraction, in which efficient solutions are bootstrapped from inefficient

solutions; and bootstrapping to aggregate types, in which implementa-

tions with atomic elements are bootstrapped to implementations with

aggregate elements.

• Chapter 11 describes implicit recursive slowdown, a lazy variant of the

recursive-slowdown technique of Kaplan and Tarjan [KT95]. As with

lazy rebuilding, implicit recursive slowdown is significantly simpler than

recursive slowdown, but yields amortized rather than worst-case bounds.

Again, we can often recover the worst-case bounds using scheduling.

Finally, Appendix A includes Haskell translations of most of the implementa-

tions in this book.

剩余230页未读，继续阅读

Mate40Pro陶瓷白

粉丝: 4

资源: 19

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益
登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

最新资源

多模态联合稀疏表示在视频目标跟踪中的应用
Kubernetes资源管控与Gardener开源软件实践解析
MPI集群监控与负载平衡策略
自动化PHP安全漏洞检测：静态代码分析与数据流方法
青苔数据CEO程永：技术生态与阿里云开放创新
制造业转型： HyperX引领企业上云策略
赵维五分享：航空工业电子采购上云实战与运维策略
单片机控制的LED点阵显示屏设计及其实现
驻云科技李俊涛：AI驱动的云上服务新趋势与挑战
6LoWPAN物联网边界路由器：设计与实现
猩便利工程师仲小玉：Terraform云资源管理最佳实践与团队协作
类差分度改进的互信息特征选择提升文本分类性能
VERITAS与阿里云合作的混合云转型与数据保护方案
云制造中的生产线仿真模型设计与虚拟化研究
汪洋在PostgresChina2018分享：高可用 PostgreSQL 工具与架构设计
2018 PostgresChina大会：阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储