Raku/Rakudo 包含哪些持久数据结构？

Question

Raku 提供了许多不可变的类型，因此在创建后无法修改。直到我最近开始研究这个领域，我的理解是这些类型不是 持久数据结构——也就是说，与 Clojure 或 Haskell 中的核心类型不同，我相信 Raku 的不可变类型没有利用结构共享来允许廉价的副本。我认为该语句my List $new = (|$old-list, 42);从字面上复制了 中的值$old-list，而没有持久数据结构的数据共享功能。

但是，由于以下代码，我对我的理解的描述是过去时：

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" }

在一次运行中产生了这个输出：

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

也就是说，用旧值创建一个新的 List 与推送到一个可变数组一样快，而且比将 List 复制到一个新的数组快得多——这正是你期望从一个数组中看到的性能特征。持久列表（复制到数组仍然很慢，因为它不能在不破坏列表不变性的情况下利用结构共享）。的快速复制$l到$nl是不是因为无论列表懒惰; 两者都不是。

以上所有让我相信 Rakudo 中的列表实际上是持久性数据结构，具有暗示的所有性能优势。这给我留下了几个问题：

• 我对列表是持久数据结构的看法正确吗？
• 所有其他不可变类型也是持久数据结构吗？或者有吗？
• 是 Raku 的任何部分，还是只是 Rakudo 做出的实施选择？
• 是否在任何地方记录/保证了这些性能特征中的任何一个？

我不得不说，我对发现至少一些 Raku(do) 类型的持久性的证据印象深刻，而且有点困惑。这是其他语言列为关键卖点的那种功能，或者导致在 GitHub 上创建具有 30k+ 星的库。我们真的在 Raku 拥有它甚至没有提到它吗？

Answer 1

我记得实现了这些语义，而且我当然不记得当时考虑过它们会产生持久性数据结构 - 尽管将该标签附加到结果似乎是公平的！

我不认为你会发现任何地方，明确地阐述了这个确切的行为，但是最自然的实现，事情是由语言需要很自然地导致它。服用成分：

• 该infix:<,>操作是List在乐构造
• 当 aList被创建时，它对于懒惰和扁平化是不置可否的（这些源于我们如何使用List，我们通常不知道在它的构造点）
• 当我们写的时候(|$x, 1)，prefix:<|>操作符构造了 a Slip，它是一种List应该融入它的周围List。因此infix:<,>看到的是 aSlip和 an Int。
• 使Slip熔体到结果List立即就意味着作出有关的渴望，这承诺List单独建设不应该这样做。因此，Slip和之后的所有内容都被放入List.

最后一个是导致观察到的持久数据结构样式行为的原因。

我希望有一个实现可以检查Slip并选择急切地复制已知不是懒惰的东西，并且仍然符合规范测试套件。这会改变你的例子的时间复杂度。如果你想对此进行防御，那么：

do { my $nl = (|$l.lazy, rand); 
     say "Appended an element to the List in $((now - ENTER now).round: .000001) seconds" }

即使实施发生了变化，也应该足以强制解决问题。

立即想到与持久数据结构或至少尾部共享相关的其他情况：

• 字符串的 MoarVM 实现，在后面str，因此Str，通过创建一个新的字符串来实现字符串连接，该字符串引用正在连接的两个字符串，而不是复制两个字符串中的数据（并且对substr和重复执行类似的技巧）。这严格来说是一种优化，而不是语言要求，并且在一些微妙的情况下（一个字符串的最后一个字素和下一个的第一个字素将在结果字符串中形成单个字素），它放弃并采用复制路径。
• 在核心之外，诸如Concurrent::Stack、Concurrent::Queue和 之类的模块Concurrent::Trie使用尾部共享作为实现相对高效的无锁数据结构的技术。