Giacomo Cavalieri (Mar 05 2023 at 17:26): Giacomo Cavalieri (Mar 05 2023 at 17:26):Hello! I finally managed to find some spare time to write some Roc, so far I really like it! One thing I'd love to try is to write Okasaki's functional pearl on RB trees
Giacomo Cavalieri (Mar 05 2023 at 17:26):From what I can recall Roc uses Perceus which should allow functional-but-in-place algorithms, and I remember seeing an example on quicksort in one of Richard's talk on youtube, can I expect the same kind of optimization to be applied to a pure functional algorithm written on a custom datatype like an RB-tree node? Or is it something that is just available for lists for now?
Brendan Hansknecht (Mar 05 2023 at 17:27):Yeah, should apply to custom types.
Brendan Hansknecht (Mar 05 2023 at 17:28):Though of course depending on how things are written can have unintentional copies.
Giacomo Cavalieri (Mar 05 2023 at 17:30):Thanks! I'll se what I can do :)
Folkert de Vries (Mar 05 2023 at 17:30):we're also not quite using perceus, but its predecessor "counting immutable beans". That means RC is a bit less efficient in some cases. But in general yes, it should work, and if it doesn't, that would be valuable to know!
Brendan Hansknecht (Mar 05 2023 at 17:32):After you write it up, if you want help debugging allocations, I have messed with that a lot.
Giacomo Cavalieri (Mar 05 2023 at 18:15):Ok so I finished writing the code it's exactly as presented in Okasaki's pearl: https://gist.github.com/giacomocavalieri/1ea3836783a2668c9fb4852de13f313d
Giacomo Cavalieri (Mar 05 2023 at 18:15):Just to make sure I get the hang of how the reuse could work, for example in the balance function it should be able to reuse the Tree constructor instead of allocating a new one?
Folkert de Vries (Mar 05 2023 at 18:26):assuming a unique input, yes
Last updated: Jul 06 2025 at 12:14 UTC