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 the best methods, we need to implement different algorithms of 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 by kindelia team 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)- Binary Search Trees (Miguel)
- Leftist Heaps (Guilherme)
Red-Black Trees (done)- Streams
- Queues (Daniel e Lucas)
Binomial Heaps (done)- Splay Heaps
- Pairing Heaps
- The Banker's Method
- The Physicist's Method
- Lazy Pairing Heaps
- Scheduling
- Real-Time Queues
- Binomial Heaps
- Bottom-Up Mergesort with Sharing
- 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)