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

也就是说，使用旧值+1创建一个新列表就像推到可变数组一样快，而且比将列表复制到新数组中要快得多--这正是您期望从持久列表中看到的性能特征(复制到Array仍然很慢，因为它不能利用结构共享而不破坏列表的不可变性)。将$l快速复制到$nl并不是因为这两个列表都是懒惰的，也不是。

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

• 关于列表是持久化的数据结构，我说得对吗？
• 是否所有其他不可变类型也都是持久的数据结构？或者有吗？
• 是Raku的这一部分，还是Rakudo所做的实现选择？
• 这些性能特性在任何地方都有记录/保证吗？

我不得不说，我对Raku (Do)的某些类型至少是持久化的证据印象深刻，也有点困惑。它是其他语言列表作为一个关键的卖点的特性，也是导致在GitHub上创建30k+星库的原因。难道我们真的在Raku中没有提到它吗？

Answer 1

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

我不认为您会发现任何地方都没有明确说明这种行为的地方，但是语言所要求的最自然的实现很自然地导致了这种行为。取原料：

• infix:<,>操作符是Raku中的List构造函数。
• 创建List时，对于懒惰和扁平化，它是不确定的(这些都来自于我们如何使用List，在构造时我们一般都不知道)。
• 当我们编写(|$x, 1)时，prefix:<|>运算符构造一个Slip，这是一种List，应该融化到其周围的List中。因此，infix:<,>看到的是一个Slip和一个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这样的模块使用尾部共享作为一种技术来实现相对高效的无锁数据结构。