Persistent collections?

1

Afaik good implementations of Finger trees and RRB vectors compare reasonably well to javascript lists, but perform much better at operations where using mutable arrays leads to O(n^2) behaviour, especially for reactive code that compares a value to the old one to detect change.

Is there a good rescript implementation of persistent data structures with rescript providing strong typing? I am sort of surprised that Belt seems to have gone for immutable-but-not-persistent, given that it also does treeshaking, since that creates a misconception that immutability provides no performance benefits

2

Belt’s Map and Set types use AVL trees which are persistent. Is that what you’re looking for?

open Belt.Set.String
let s1 = empty->add("x")->add("y")->add("z")
let s2 = s1->add("a")
let s3 = s1->add("b")

In this example, the “y” and “z” parts of the set are persistent across all three structures. You can verify that by debugging the JS output.

3

Here persistent vector and WIP finger-tree based queue implementation

cc @namenu

3 Likes