Skip header Section
Skip Bibliometrics Section
Purely Functional Data StructuresJune 1999
- Author:
- Chris Okasaki
Skip Abstract Section
Abstract
From the Publisher:
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.
Cited By
- Haselwarter P, Li K, de Medeiros M, Gregersen S, Aguirre A, Tassarotti J and Birkedal L (2024). Tachis: Higher-Order Separation Logic with Credits for Expected Costs, Proceedings of the ACM on Programming Languages, 8:OOPSLA2, (1189-1218), Online publication date: 8-Oct-2024.
- Exelmans J, Pietron J, Raschke A and Vangheluwe H A Virtual Global Monorepo of Immutable Linked Data Proceedings of the ACM/IEEE 27th International Conference on Model Driven Engineering Languages and Systems, (1000-1004)
- van Brügge J Liquid Amortization: Proving Amortized Complexity with LiquidHaskell (Functional Pearl) Proceedings of the 17th ACM SIGPLAN International Haskell Symposium, (97-108)
- Elsman M (2024). Double-Ended Bit-Stealing for Algebraic Data Types, Proceedings of the ACM on Programming Languages, 8:ICFP, (88-120), Online publication date: 15-Aug-2024.
- Xia L, Israel L, Kramarz M, Coltharp N, Claessen K, Weirich S and Li Y (2024). Story of Your Lazy Function’s Life: A Bidirectional Demand Semantics for Mechanized Cost Analysis of Lazy Programs, Proceedings of the ACM on Programming Languages, 8:ICFP, (30-63), Online publication date: 15-Aug-2024.
- Zhou Z, Ye Q, Delaware B and Jagannathan S (2024). A HAT Trick: Automatically Verifying Representation Invariants using Symbolic Finite Automata, Proceedings of the ACM on Programming Languages, 8:PLDI, (1387-1411), Online publication date: 20-Jun-2024.
- Lorenzen A, Leijen D, Swierstra W and Lindley S (2024). The Functional Essence of Imperative Binary Search Trees, Proceedings of the ACM on Programming Languages, 8:PLDI, (518-542), Online publication date: 20-Jun-2024.
- Brodal G, Rysgaard C, Schou J and Svenning R Space-Efficient Functional Offline-Partially-Persistent Trees with Applications to Planar Point Location Algorithms and Data Structures, (644-659)
- Charguéraud A (2023). Review on Functional Algorithms, Verified!, Formal Aspects of Computing, 35:2, (1-2), Online publication date: 30-Jun-2023.
- Pedersen J and Conradt J AEStream: Accelerated event-based processing with coroutines Proceedings of the 2023 Annual Neuro-Inspired Computational Elements Conference, (86-91)
- Aksenov V, Brown T, Fedorov A and Kokorin I Unexpected Scaling in Path Copying Trees Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, (438-440)
- Nelson-Slivon J, Hassan A and Palmieri R Bundling linked data structures for linearizable range queries Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, (368-384)
- Biernacka M, Charatonik W and Drab T A Derived Reasonable Abstract Machine for Strong Call by Value Proceedings of the 23rd International Symposium on Principles and Practice of Declarative Programming, (1-14)
- Leutgeb L, Moser G and Zuleger F ATLAS: Automated Amortised Complexity Analysis of Self-adjusting Data Structures Computer Aided Verification, (99-122)
- Pitzer E and Affenzeller M Cheating Like The Neighbors: Logarithmic Complexity For Fitness Evaluation In Genetic Algorithms 2021 IEEE Congress on Evolutionary Computation (CEC), (1431-1438)
- Reinking A, Xie N, de Moura L and Leijen D Perceus: garbage free reference counting with reuse Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, (96-111)
- Piantadosi S (2021). The Computational Origin of Representation, Minds and Machines, 31:1, (1-58), Online publication date: 1-Mar-2021.
- Biernacka M, Biernacki D, Charatonik W and Drab T An Abstract Machine for Strong Call by Value Programming Languages and Systems, (147-166)
- Agrawal A, Li Y, Xue J and Janardan R (2020). The most-likely skyline problem for stochastic points, Computational Geometry: Theory and Applications, 88:C, Online publication date: 1-Jun-2020.
- Ma T, Zhang M, Chen K, Song Z, Wu Y and Qian X AsymNVM Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, (757-773)
- Haria S, Hill M and Swift M MOD Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, (775-788)
- Hamza J, Voirol N and Kunčak V (2019). System FR: formalized foundations for the stainless verifier, Proceedings of the ACM on Programming Languages, 3:OOPSLA, (1-30), Online publication date: 10-Oct-2019.
- Kaki G, Priya S, Sivaramakrishnan K and Jagannathan S (2019). Mergeable replicated data types, Proceedings of the ACM on Programming Languages, 3:OOPSLA, (1-29), Online publication date: 10-Oct-2019.
- Sun Y, Blelloch G, Lim W and Pavlo A (2019). On supporting efficient snapshot isolation for hybrid workloads with multi-versioned indexes, Proceedings of the VLDB Endowment, 13:2, (211-225), Online publication date: 1-Oct-2019.
- Yallop J and White L (2019). Lambda: the ultimate sublanguage (experience report), Proceedings of the ACM on Programming Languages, 3:ICFP, (1-17), Online publication date: 26-Jul-2019.
- Hackett J and Hutton G (2019). Call-by-need is clairvoyant call-by-value, Proceedings of the ACM on Programming Languages, 3:ICFP, (1-23), Online publication date: 26-Jul-2019.
- Balakrishnan D, Ziarek L and Kennedy O Fluid data structures Proceedings of the 17th ACM SIGPLAN International Symposium on Database Programming Languages, (3-17)
- Ben-David N, Blelloch G, Sun Y and Wei Y Multiversion Concurrency with Bounded Delay and Precise Garbage Collection The 31st ACM Symposium on Parallelism in Algorithms and Architectures, (241-252)
- Pereira R, Couto M, Cunha J, Melfe G, Saraiva J and Fernandes J Paint Your Programs Green: On the Energy Efficiency of Data Structures Composability, Comprehensibility and Correctness of Working Software, (53-76)
- Charguéraud A and Pottier F (2019). Verifying the Correctness and Amortized Complexity of a Union-Find Implementation in Separation Logic with Time Credits, Journal of Automated Reasoning, 62:3, (331-365), Online publication date: 1-Mar-2019.
- Pitzer E and Affenzeller M “Incremental” Evaluation for Genetic Crossover Computer Aided Systems Theory – EUROCAST 2019, (396-404)
- Newton J and Verna D (2019). A Theoretical and Numerical Analysis of the Worst-Case Size of Reduced Ordered Binary Decision Diagrams, ACM Transactions on Computational Logic, 20:1, (1-36), Online publication date: 31-Jan-2019.
- Steindorfer M and Vinju J (2018). To-many or to-one? all-in-one! efficient purely functional multi-maps with type-heterogeneous hash-tries, ACM SIGPLAN Notices, 53:4, (283-295), Online publication date: 2-Dec-2018.
- Breitner J, Spector-Zabusky A, Li Y, Rizkallah C, Wiegley J and Weirich S (2018). Ready, set, verify! applying hs-to-coq to real-world Haskell code (experience report), Proceedings of the ACM on Programming Languages, 2:ICFP, (1-16), Online publication date: 30-Jul-2018.
- Winblad K, Sagonas K and Jonsson B Lock-free Contention Adapting Search Trees Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, (121-132)
- Steindorfer M and Vinju J To-many or to-one? all-in-one! efficient purely functional multi-maps with type-heterogeneous hash-tries Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, (283-295)
- Wang S, Dinh T, Lin Q, Xie Z, Zhang M, Cai Q, Chen G, Ooi B and Ruan P (2018). Forkbase, Proceedings of the VLDB Endowment, 11:10, (1137-1150), Online publication date: 1-Jun-2018.
- Peng Y, Guo J, Li F, Qian W and Zhou A Persistent Bloom Filter Proceedings of the 2018 International Conference on Management of Data, (1037-1052)
- Peng J, Ge J, He W, Chen Z, Liu C and Chen G (2018). A Fine-Grained Stateful Data Analytics Method Based on Resilient State Table, International Journal of Software Science and Computational Intelligence, 10:2, (66-79), Online publication date: 1-Apr-2018.
- Sun Y, Ferizovic D and Belloch G (2018). PAM, ACM SIGPLAN Notices, 53:1, (290-304), Online publication date: 23-Mar-2018.
- Wen H, Izraelevitz J, Cai W, Beadle H and Scott M (2018). Interval-based memory reclamation, ACM SIGPLAN Notices, 53:1, (1-13), Online publication date: 23-Mar-2018.
- Sun Y, Ferizovic D and Belloch G PAM Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, (290-304)
- Wen H, Izraelevitz J, Cai W, Beadle H and Scott M Interval-based memory reclamation Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, (1-13)
- Spector-Zabusky A, Breitner J, Rizkallah C and Weirich S Total Haskell is reasonable Coq Proceedings of the 7th ACM SIGPLAN International Conference on Certified Programs and Proofs, (14-27)
- Gawrychowski P, Karczmarz A, Kociumaka T, Łącki J and Sankowski P Optimal dynamic strings Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, (1509-1528)
- Zhang X and Guo P DS.js Proceedings of the 30th Annual ACM Symposium on User Interface Software and Technology, (691-702)
- Chrząszcz J and Schubert A Function definitions for compound values in object-oriented languages Proceedings of the 19th International Symposium on Principles and Practice of Declarative Programming, (61-72)
- Goldstein M, Dayan D, Rabin M, Berlowitz D, Berlowitz O and Yehezkael R Design principles of an embedded language (EFL) enabling well defined order-independent execution Proceedings of the Fifth European Conference on the Engineering of Computer-Based Systems, (1-8)
- Blanchette J, Meier F, Popescu A and Traytel D Foundational nonuniform (co)datatypes for higher-order logic Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, (1-12)
- Steindorfer M and Vinju J (2016). Towards a software product line of trie-based collections, ACM SIGPLAN Notices, 52:3, (168-172), Online publication date: 12-May-2017.
- Chang S, Knauth A and Greenman B (2017). Type systems as macros, ACM SIGPLAN Notices, 52:1, (694-705), Online publication date: 11-May-2017.
- Chang S, Knauth A and Greenman B Type systems as macros Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, (694-705)
- Mu S, Chiang Y and Lyu Y (2016). Queueing and glueing for optimal partitioning (functional pearl), ACM SIGPLAN Notices, 51:9, (158-167), Online publication date: 5-Dec-2016.
- Tsesko V and Demidov S YoctoDB Proceedings of the 12th Central and Eastern European Software Engineering Conference in Russia, (1-10)
- Steindorfer M and Vinju J Towards a software product line of trie-based collections Proceedings of the 2016 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences, (168-172)
- Mu S, Chiang Y and Lyu Y Queueing and glueing for optimal partitioning (functional pearl) Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming, (158-167)
- Akkoorath D and Bieniusa A Highly-scalable concurrent objects Proceedings of the 2nd Workshop on the Principles and Practice of Consistency for Distributed Data, (1-4)
- Steindorfer M and Vinju J Performance Modeling of Maximal Sharing Proceedings of the 7th ACM/SPEC on International Conference on Performance Engineering, (135-146)
- Charguéraud A Higher-order representation predicates in separation logic Proceedings of the 5th ACM SIGPLAN Conference on Certified Programs and Proofs, (3-14)
- Steindorfer M and Vinju J (2015). Optimizing hash-array mapped tries for fast and lean immutable JVM collections, ACM SIGPLAN Notices, 50:10, (783-800), Online publication date: 18-Dec-2015.
- Steindorfer M and Vinju J Optimizing hash-array mapped tries for fast and lean immutable JVM collections Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, (783-800)
- Hofmann M Automatic amortized analysis Proceedings of the 17th International Symposium on Principles and Practice of Declarative Programming, (5-5)
- Aref M, ten Cate B, Green T, Kimelfeld B, Olteanu D, Pasalic E, Veldhuizen T and Washburn G Design and Implementation of the LogicBlox System Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, (1371-1382)
- Green T LogiQL Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, (59-64)
- Steindorfer M and Vinju J (2014). Code specialization for memory efficient hash tries (short paper), ACM SIGPLAN Notices, 50:3, (11-14), Online publication date: 12-May-2015.
- Hackett J and Hutton G (2014). Worker/wrapper/makes it/faster, ACM SIGPLAN Notices, 49:9, (95-107), Online publication date: 26-Nov-2014.
- Lorenz D and Rosenan B Versionable, Branchable, and Mergeable Application State Proceedings of the 2014 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software, (29-42)
- Steindorfer M and Vinju J Code specialization for memory efficient hash tries (short paper) Proceedings of the 2014 International Conference on Generative Programming: Concepts and Experiences, (11-14)
- Totoo P and Loidl H Lazy data-oriented evaluation strategies Proceedings of the 3rd ACM SIGPLAN workshop on Functional high-performance computing, (63-74)
- Hackett J and Hutton G Worker/wrapper/makes it/faster Proceedings of the 19th ACM SIGPLAN international conference on Functional programming, (95-107)
- Kemme B, Schiper A, Ramalingam G and Shapiro M (2014). Dagstuhl seminar review, ACM SIGACT News, 45:1, (67-89), Online publication date: 17-Mar-2014.
- Solodkyy Y, Dos Reis G and Stroustrup B (2013). Open pattern matching for C++, ACM SIGPLAN Notices, 49:3, (33-42), Online publication date: 5-Mar-2014.
- Kneuss E, Kuraj I, Kuncak V and Suter P (2013). Synthesis modulo recursive functions, ACM SIGPLAN Notices, 48:10, (407-426), Online publication date: 12-Nov-2013.
- Kneuss E, Kuraj I, Kuncak V and Suter P Synthesis modulo recursive functions Proceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications, (407-426)
- Solodkyy Y, Dos Reis G and Stroustrup B Open pattern matching for C++ Proceedings of the 12th international conference on Generative programming: concepts & experiences, (33-42)
- O'Donnell J Extensible sparse functional arrays with circuit parallelism Proceedings of the 15th Symposium on Principles and Practice of Declarative Programming, (133-144)
- Holdermans S Random testing of purely functional abstract datatypes Proceedings of the 15th Symposium on Principles and Practice of Declarative Programming, (275-284)
- Bloom B and Hirzel M (2012). Robust scripting via patterns, ACM SIGPLAN Notices, 48:2, (29-40), Online publication date: 23-Jan-2013.
- Bloom B and Hirzel M Robust scripting via patterns Proceedings of the 8th symposium on Dynamic languages, (29-40)
- Prokopec A, Bronson N, Bagwell P and Odersky M (2012). Concurrent tries with efficient non-blocking snapshots, ACM SIGPLAN Notices, 47:8, (151-160), Online publication date: 11-Sep-2012.
- Byrd W, Holk E and Friedman D miniKanren, live and untagged Proceedings of the 2012 Annual Workshop on Scheme and Functional Programming, (8-29)
- Prokopec A, Bronson N, Bagwell P and Odersky M Concurrent tries with efficient non-blocking snapshots Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming, (151-160)
- Charguéraud A Characteristic formulae for the verification of imperative programs Proceedings of the 16th ACM SIGPLAN international conference on Functional programming, (418-430)
- Charguéraud A (2011). Characteristic formulae for the verification of imperative programs, ACM SIGPLAN Notices, 46:9, (418-430), Online publication date: 18-Sep-2011.
- Crosby S and Wallach D (2011). Authenticated Dictionaries, ACM Transactions on Information and System Security, 14:2, (1-30), Online publication date: 1-Sep-2011.
- Warth A, Ohshima Y, Kaehler T and Kay A Worlds Proceedings of the 25th European conference on Object-oriented programming, (179-203)
- Venkataraman S, Tolia N, Ranganathan P and Campbell R Consistent and durable data structures for non-volatile byte-addressable memory Proceedings of the 9th USENIX conference on File and stroage technologies, (5-5)
- Pilkiewicz A and Pottier F The essence of monotonic state Proceedings of the 7th ACM SIGPLAN workshop on Types in language design and implementation, (73-86)
- Straka M (2010). The performance of the Haskell containers package, ACM SIGPLAN Notices, 45:11, (13-24), Online publication date: 17-Nov-2010.
- Straka M The performance of the Haskell containers package Proceedings of the third ACM Haskell symposium on Haskell, (13-24)
- Charguéraud A (2010). Program verification through characteristic formulae, ACM SIGPLAN Notices, 45:9, (321-332), Online publication date: 27-Sep-2010.
- Charguéraud A Program verification through characteristic formulae Proceedings of the 15th ACM SIGPLAN international conference on Functional programming, (321-332)
- Crosby S and Wallach D Super-efficient aggregating history-independent persistent authenticated dictionaries Proceedings of the 14th European conference on Research in computer security, (671-688)
- Bernardy J Lazy functional incremental parsing Proceedings of the 2nd ACM SIGPLAN symposium on Haskell, (49-60)
- Gazagnaire T and Hanquez V (2009). OXenstored, ACM SIGPLAN Notices, 44:9, (203-214), Online publication date: 31-Aug-2009.
- Gazagnaire T and Hanquez V OXenstored Proceedings of the 14th ACM SIGPLAN international conference on Functional programming, (203-214)
Please enable JavaScript to view thecomments powered by Disqus.
Recommendations
Purely functional lazy nondeterministic programming
Dedicated to ICFP 2009Functional logic programming and probabilistic programming have demonstrated the broad benefits of combining laziness (nonstrict evaluation with sharing of the results) with nondeterminism. Yet these benefits are seldom enjoyed in functional programming ...
Purely functional lazy non-deterministic programming
ICFP '09Functional logic programming and probabilistic programming have demonstrated the broad benefits of combining laziness (non-strict evaluation with sharing of the results) with non-determinism. Yet these benefits are seldom enjoyed in functional ...