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

Question

Raku 提供 many类型是 immutable因此在创建后无法修改。直到我最近开始研究这个领域，我的理解是这些类型不是 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

也就是说，用旧值创建一个新的 List 与推送到一个可变数组一样快，而且比将 List 复制到一个新的数组快得多——这正是你期望从一个数组中看到的性能特征。持久列表(复制到数组仍然很慢，因为它不能在不破坏列表不变性的情况下利用结构共享)。 $l的快速复制进入 $nl不是因为 List 懒惰；两者都不是。
以上所有让我相信 Rakudo 中的列表实际上是持久性数据结构，具有暗示的所有性能优势。这给我留下了几个问题:

我对列表是持久数据结构的看法正确吗？

所有其他不可变类型也是持久数据结构吗？或者有吗？

是 Raku 的任何部分，还是只是 Rakudo 做出的实现选择？

是否在任何地方记录/保证了这些性能特征中的任何一个？

我不得不说，我对发现至少一些 Raku(do) 类型的持久性的证据印象深刻，而且有点困惑。这是其他语言的特性 list as a key selling point或者导致创建 libraries with 30k+ stars在 GitHub 上。我们真的在 Raku 拥有它甚至没有提到它吗？

Answer 1

我记得实现了这些语义，而且我当然不记得当时考虑过它们会产生持久性数据结构 - 尽管将该标签附加到结果似乎是公平的!
我认为您找不到任何明确说明这种确切行为的地方，但是语言所需的事物的最自然实现很自然地会导致它。服用成分:

infix:<,>运算符是 List Raku 中的构造函数

当List被创建后，它对懒惰和扁平化不置可否(这些源于我们如何使用 List ，我们通常不知道它的构造点)

当我们写 (|$x, 1) , prefix:<|>运算符构造一个 Slip ，这是一种 List应该融入周围 List .那么什么infix:<,>看到的是 Slip和一个 Int .

制作 Slip融入结果List立即意味着对渴望做出 promise ，即 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使用尾部共享作为实现相对高效的无锁数据结构的技术。