@dimitri.lozeve has joined the channel
Oh, I don’t like some
at all (no pun intended)! To me it implies more than one :)
Aww… many thanks. Let’s be fair, though: Matthias told me to write it :slightly_smiling_face:
Just came across this tutorial and noticed that the functional implementation is much slower than the imperative one. Wonder if there is any way to make it faster without sacrificing purity. https://beautifulracket.com/bf/a-functional-expander.html
I think you want to use things like Okasaki’s random access list rather than a list or a vector here.
Accessing and setting in the random access list can be done in O(log n).
If you use regular list, both accessing and setting takes O(i) = O(n) in worst case.
If you use vector, accessing takes O(1), but setting takes O(n) (in case you want it to be functional, not imperative).
Oh, there’s a random access list library in Racket already too: https://docs.racket-lang.org/ralist/
Or Braun trees!