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

Question

Raku 提供 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——也就是说，与 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

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

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

关于列表是持久数据结构，我说得对吗？
是否所有其他不可变类型也持久数据结构？或者有吗？
这是 Raku 的任何一部分，还是只是 Rakudo 做出的实施选择？
这些性能特征 documented/guaranteed 有吗？

我不得不说，发现证据表明至少有一些 Raku(do) 的类型是持久的，我既印象深刻又有点困惑。这是其他语言 list as a key selling point or that leads to the creation of libraries with 30k+ stars 在 GitHub 上的那种特性。我们真的在 Raku 甚至没有提及它吗？

Answer 1

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

我认为您不会在任何地方找到明确说明这种确切行为的地方，但是语言所要求的事物的最自然实现很自然地导致它。服用原料：

infix:<,> 运算符是 RakuList 中的构造函数
当创建 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 等模块使用尾部共享作为实现相对高效的无锁数据结构的技术。

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

What persistent data structures does Raku/Rakudo include?

functional-programming

immutability

raku

rakudo