Purely Functional Data Structures
Table of Contents
- 1. Background
- 2. Code
- 3. Implementation
- 3.1. Pair
- 3.2. Node
- 3.3. LinkedList
- 3.4. List
- 3.5. Association List
- 3.6. Map
- 3.7. Object
- 3.8. Set
- 3.9. Sequence
- 3.10. Collection
- 3.11. Stack
- 3.12. Record
- 3.13. Queue
- 3.14. Binary Search Tree
- 3.15. Trie
- 3.16. Persistent List
- 3.17. Persistent Binary Search Tree
- 3.18. Leftist Heaps
- 3.19. Binomial Heaps
- 3.20. Splay Heaps
- 3.21. Red-Black Trees
- 4. Examples
- 5. API
1. Background
Implement persistent data structures with limited use of host data structures (other than function definition and simple data types).
This works off of Okasaki's "Purely Functional Data Structures" and Immutable.js.
2. Code
https://github.com/jwalsh/pfds.js returns 404 as of verification. Neither the GitHub API nor a repository-name search finds a "pfds.js" repo under the jwalsh account, so the implementation this note points to does not currently exist at this location.
3. Implementation
3.1. Pair
https://github.com/jwalsh/pairs.js returns 404 (no such repo exists under the jwalsh account). The hexlet-components/js-pairs repo does exist, but the cited path is wrong on two counts: its default branch is =main=, not =master=, and the source file is =index.ts=, not =index.js= — corrected below.
3.2. Node
3.3. LinkedList
3.4. List
3.5. Association List
3.6. Map
3.7. Object
3.8. Set
3.9. Sequence
3.10. Collection
3.11. Stack
3.12. Record
3.13. Queue
3.14. Binary Search Tree
3.15. Trie
3.16. Persistent List
3.18. Leftist Heaps
3.19. Binomial Heaps
3.20. Splay Heaps
3.21. Red-Black Trees
4. Examples
5. API
=#L49= no longer points at the =first= definition. core.clj has grown since this link was written; on the current master branch =first= is defined at line 55 — corrected below.
https://github.com/clojure/clojure/blob/master/src/clj/clojure/core.clj#L55
- first
- next
- rest
- second
- ffirst
- nfirst
- fnext