What persistent data structures does Raku/Rakudo include?

14

Raku provides many types that are immutable and thus cannot be modified after they are created. Until I started looking into this area recently, my understanding was that these Types were not persistent data structures – that is, unlike the core types in Clojure or Haskell, my belief was that Raku's immutable types did not take advantage of structural sharing to allow for inexpensive copies. I thought that statement my List $new = (|$old-list, 42); literally copied the values in $old-list, without the data-sharing features of persistent data structures.

That description of my understanding is in the past tense, however, due to the following code:

my Array $a = do {
    $_ = [rand xx 10_000_000];
    say "Initialized an Array in $((now - ENTER now).round: .001) seconds"; $_}
my List $l = do {
    $_ = |(rand xx 10_000_000);
    say "Initialized the List in $((now - ENTER now).round: .001) seconds"; $_}
do { $a.push: rand;  
     say "Pushed the element to the Array in $((now - ENTER now).round: .000001) seconds" }
do { my $nl = (|$l, rand); 
     say "Appended an element to the List in $((now - ENTER now).round: .000001) seconds" }
do { my @na = |$l; 
     say "Copied List \$l into a new Array in $((now - ENTER now).round: .001) seconds" }

which produced this output in one run:

Initialized an Array in 5.938 seconds
Initialized the List in 5.639 seconds
Pushed the element to the Array in 0.000109 seconds
Appended an element to the List in 0.000109 seconds
Copied List $l into a new Array in 11.495 seconds

That is, creating a new List with the old values + one more is just as fast as pushing to a mutable Array, and dramatically faster than copying the List into a new Array – exactly the performance characteristics that you'd expect to see from a persistent List (copying to an Array is still slow because it can't take advantage of structural sharing without breaking the immutability of the List). The fast copying of $l into $nl is not due to either List being lazy; neither are.

All of the above leads me to believe that Lists in Rakudo actually are persistent data structures, with all the performance benefits that implies. That leaves me with several questions:

• Am I right about Lists being persistent data structures?
• Are all other immutable Types also persistent data structures? Or are any?
• Is any of this part of Raku, or just an implementation choice Rakudo has made?
• Are any of these performance characteristics documented/guaranteed anywhere?

I have to say, I am both extremely impressed and more than a bit baffled to discover evidence that at least some of Raku(do)'s types are persistent. It's the sort of feature that other languages list as a key selling point or that leads to the creation of libraries with 30k+ stars on GitHub. Have we really had it in Raku without even mentioning it?

functional-programming immutability raku rakudo

Share

Improve this question

asked Apr 10 at 3:12

codesectionscodesections

2,46544 silver badges1717 bronze badges

4

• By definition, it won't be a "persistent" data structure unless it is absolutely protected from Garbage Collection, correct? – jubilatious1 Apr 10 at 15:40
• 1
  @codesections "The fast copying of $l into $nl is not due to either List being lazy; neither are." Are you relying on .is-lazy? Per its doc, with my added emphasis, is-lazy "Returns True if and only if the underlying iterator or cached list [or sequence] considers itself lazy.", but see also my answer to SO "About Laziness", and behaviour I've made visible by using a modified version of your code. – raiph Apr 10 at 17:27
• I'm curious if you haven't accepted jnthn's answer because you're hoping for something else. If so, I for one am curious to read a comment by you providing a brief summary of what you feel's missing (or maybe accept jnthn's answer and write a fresh Q). – raiph Apr 14 at 23:47
• @jubilatious1: How does that property follow from the definition of a persistent data structure? The only real requirement for a persistent data structure is that if I have a reference to it, and someone else modifies the data structure, I should still have access to my version of it. We generally also require that operations are efficient (i.e. comparable to an equivalent non-persistent data structure) and that all versions are equally efficient, but those are desirable properties, not technically part of the definition. – Jörg W Mittag Apr 17 at 6:06

Add a comment  |