Purely Functional Data Structures
Cambridge University Press, 1998年4月13日
Most books on data structures assume an imperative language like 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 so that programmers can develop their own functional data structures. It 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 can easily be adapted 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.
讀者評論 - 撰寫評論
其他版本 - 查看全部
algorithms amortized bounds amortized cost amortized data structures balance banker’s method binary numbers binary randomaccess lists binary search trees binomial heaps binomial tree bootstrapped catenable catenable lists Chapter checkQ complete binary computation cons constructor contains copy datatype deleted deleteMin deques digit discharged efficient error empty example exec exec2 execute Exercise Figure findMin finite maps force front functor global rebuilding head helper function Ienr implementation incremental insert insTree inthe isEmpty languages lazy evaluation leaf leftist heaps lent t lenr lookup memoization merge mergesort monolithic node nonempty nonzero number of debits numerical representations ofthe operation pairing heaps PairingHeap persistent persistent data structures physicist’s method potential purely functional realtime queues removeMinTree represent reverse root rotation run in O(log runs in O(1 schedule Section segment sequence SHALLOW signature simply skew binary snoc splay trees Standard ML subtree tail takes Tarjan technique tree of rank trie unshared cost update worstcase bounds zero