To complete HVM development, we need to decide which purely functional data structures are going to be used on Kindelia to handle access information on memory.
The image below represents partially what we are interested in:
To decide which methods work better, we need to implement different algorithms and data structures and compare the number of "rewrites" and "memory" wasted.
A great source of functional algorithms with examples is the Okasaki Book (other links), and this list of links.
There is a video tutorial (in portuguese), made a Kindelia team member, explaining how to implement the patricia tree, based on this paper.
There isn't a language since it's been built from zero, and it's not necessary on functional programing.
Anyway, there are some functions which are been used repeatedly, maybe you can find more about then on kind repository.
Lists (done)Bottom-Up Mergesort (done)Sortable Collections with Bottom-Up Mergesort(done)
- Binary Search Trees (Miguel)
Leftist Heaps (done)Red-Black Trees (done)- Streams
- Queues (Daniel e Lucas)
Binomial Heaps (done)- Splay Heaps
Pairing Heaps (done)
- Lazy Pairing Heaps
- Scheduling
- Real-Time Queues
- Batched Rebuilding
- Global Rebuilding
- Lazy rebuilding
- Double-Ended Queues
- Positional Number systems
- Binary Numbers
- Skew Binary Numbers
- Trinary and Quaternary Numbers
- Structural Decomposition
- Structural Abstraction
- Bootstrapping to aggregate Types
- Queues and Deques
- Catenable Double-ended Queues
IntMap (done)- Finger Trees (Santi)
- Ideal Hash Trees
- Priority Search Queues
- Bootstrapping one-sided flexible arrays
- New catenable and non-catenable deques
- Maxiphobic heaps
- Purely Functional Worst Case Constant Time Catenable Sorted Lists
- Confluently Persistent Tries for Efficient Version Control
- A new purely functional delete algorithm for red-black trees
- RRB-Trees: Efficient Immutable Vectors
- Data List (Igor)
- Biased Search Trees (Guilherme, but if anyone wants to work on it, go ahead)
Patricia Tree (done)List Zipper (done)