Purely Functional Data Structures.pdf

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：5.54M 资料格式：pdf 举报版权申诉

6d101797-009c-450a-b7e1-22c746263201.pdf-第1页.png

第1页 / 共231页

6d101797-009c-450a-b7e1-22c746263201.pdf-第2页.png

第2页 / 共231页

6d101797-009c-450a-b7e1-22c746263201.pdf-第3页.png

第3页 / 共231页

6d101797-009c-450a-b7e1-22c746263201.pdf-第4页.png

第4页 / 共231页

6d101797-009c-450a-b7e1-22c746263201.pdf-第5页.png

第5页 / 共231页

6d101797-009c-450a-b7e1-22c746263201.pdf-第6页.png

第6页 / 共231页

6d101797-009c-450a-b7e1-22c746263201.pdf-第7页.png

第7页 / 共231页

6d101797-009c-450a-b7e1-22c746263201.pdf-第8页.png

第8页 / 共231页

文本预览

PURELY FUNCTIONAL DATA STRUCTURES 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.

PURELY FUNCTIONAL DATA STRUCTURES CHRIS OKASAKI COLUMBIA UNIVERSITY CAMBRIDGE UNIVERSITY PRESS

PUBLISHED BY THE PRESS SYNDICATE OF THE UNIVERSITY OF CAMBRIDGE The Pitt Building, Trumpington Street, Cambridge, United Kingdom CAMBRIDGE UNIVERSITY PRESS The Edinburgh Building, Cambridge CB2 2RU, UK www.cup.cam.ac.uk 40 West 20th Street, New York, NY 10011-4211, USA www.cup.org 10 Stamford Road, Oakleigh, Melbourne 3166, Australia Ruiz de Alarc6n 13, 28014 Madrid, Spain © Cambridge University Press 1998 This book is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published 1998 First paperback edition 1999 Typeface Times 10/13 pt. A catalog record for this book is available from the British Library Library of Congress Cataloging in Publication data is available ISBN 0 521 63124 6 hardback ISBN 0 521 66350 4 paperback Transferred to digital printing 2003

Contents Preface Imperative Data Structures Evaluation Functional vs. Strict vs. Lazy Terminology Approach Overview Trees Introduction 1.1 1.2 1.3 1.4 1.5 Persistence 2.1 Lists Binary Search 2.2 Chapter Notes 2.3 Some Familiar Data Structures in a Functional Setting 3.1 Leftist Heaps 3.2 Binomial Heaps 3.3 Red-Black Trees 3.4 Chapter Notes Lazy Evaluation 4.1 4.2 4.3 Fundamentals of Amortization 5.1 5.2 5.3 5.4 5.5 Techniques of Amortized Analysis Queues Binomial Heaps Splay Heaps Pairing Heaps $-notation Streams Chapter Notes page ix 1 1 2 3 4 4 7 7 11 15 17 17 20 24 29 31 31 34 37 39 39 42 45 46 52

vi Contents 5.6 The Bad News 5.7 Chapter Notes 6 Amortization and Persistence via Lazy Evaluation 6.1 Execution Traces and Logical Time 6.2 Reconciling Amortization and Persistence 6.2.1 The Role of Lazy Evaluation 6.2.2 A Framework for Analyzing Lazy Data Structures 6.3 The Banker's Method Justifying the Banker's Method 6.3.1 6.3.2 Example: Queues 6.3.3 Debit Inheritance 6.4 The Physicist's Method 6.4.1 Example: Binomial Heaps 6.4.2 Example: Queues 6.4.3 Example: Bottom-Up Mergesort with Sharing 6.5 Lazy Pairing Heaps 6.6 Chapter Notes 7 Eliminating Amortization 7.1 Scheduling 7.2 Real-Time Queues 7.3 Binomial Heaps 7.4 Bottom-Up Mergesort with Sharing 7.5 Chapter Notes 8 Lazy Rebuilding 8.1 Batched Rebuilding 8.2 Global Rebuilding 8.2.1 Example: Hood-Melville Real-Time Queues 8.3 Lazy Rebuilding 8.4 Double-Ended Queues 8.4.1 Output-Restricted Deques 8.4.2 Banker's Deques 8.4.3 Real-Time Deques 8.5 Chapter Notes 9 Numerical Representations 9.1 Positional Number Systems 9.2 Binary Numbers 9.2.1 Binary Random-Access Lists 9.2.2 Zeroless Representations 54 55 57 57 58 59 59 61 62 64 67 68 70 72 74 79 81 83 84 86 89 94 97 99 99 101 102 104 106 107 108 111 113 115 116 116 119 122

Contents 9.2.3 Lazy Representations 9.2.4 Segmented Representations 9.3 Skew Binary Numbers 9.3.1 Skew Binary Random-Access Lists 9.3.2 Skew Binomial Heaps 9.4 Trinary and Quaternary Numbers 9.5 Chapter Notes 10 Data-Structural Bootstrapping 10.1 Structural Decomposition 10.1.1 Non-Uniform Recursion and Standard ML 10.1.2 Binary Random-Access Lists Revisited 10.1.3 Bootstrapped Queues 10.2 Structural Abstraction 10.2.1 Lists With Efficient Catenation 10.2.2 Heaps With Efficient Merging 10.3 Bootstrapping To Aggregate Types 10.3.1 Tries 10.3.2 Generalized Tries 10.4 Chapter Notes 11 Implicit Recursive Slowdown 11.1 Queues and Deques 11.2 Catenable Double-Ended Queues 11.3 Chapter Notes A Haskell Source Code Bibliography Index vii 125 127 130 132 134 138 140 141 142 143 144 146 151 153 158 163 163 166 169 171 171 175 184 185 207 217

分享到：

赞收藏

资料库

Purely Functional Data Structures.pdf

相关推荐

课程资源

热门标签

最新资料