raku - 为什么 :{} create a "Hash[Mu,Any]" object (and what is it and how does it compare to a normal "Hash")?

Question

起初，我只是想知道为什么在这段代码(来自 Perl 6 Advent Calendar, December 25, 2018 )的第 2 行中的空大括号之前有一个冒号？

sub is-happy( $n is copy ) {
    my $seen-numbers = :{};
    while $n > 1 {
        return False if $n ∈ $seen-numbers;
        $seen-numbers{$n} = True;
        $n = $n.comb.map(*²).sum
    }
    return True;
}

say is-happy(7);     # True
say is-happy(2018);  # False

这段代码几乎立即运行。我试过 say $seen-numbers.^name;发现是Hash[Mu,Any] .

但是，当我删除冒号时，is-happy(7)返回 True ，然后 is-happy(2018)占用 CPU 几分钟(直到我终止进程)。
此外，在这种情况下，say $seen-numbers.^name;版画 Hash .

所以，很明显，:{}结果创建了一个 Hash[Mu,Any] .这是如何运作的？这是一种解决方法还是惯用的方法？什么是 Hash[Mu,Any]以及它与普通 Hash 相比如何?

Answer 1

一个 Hash有 Str键。任何不是 Str 的键在将值存储在该字符串键下之前，将被强制为 1。 {}构造一个空 Hash .

这种行为可以通过提供 Hash 来改变。类型参数。一个 Hash[Int]例如，仍然具有自动强制字符串键，但只能存储 Int值(很像 Array[Int] 只能存储 Int 值)。也可以传递第二个类型参数来选择键的类型。这会创建通常称为“对象哈希”的内容，并存储索引器中提供的确切键。所以一个 Hash[Mu,Any]是具有不受约束的值和 Any 的散列一种键(几乎所有类型都属于 Any ，但 Junction 除外)。 .WHICH key 用于散列。

大多数情况下，人们不会使用 Hash[TValue,TKey] 创建对象哈希。 ，而是使用声明语法；例如，我可能会使用类似 has Array %!edges-from{Mu} 的东西来表示 DAG 中的边。 .还有一种创建匿名对象哈希的方法，:{} ，这就是您在示例中观察到的。

那么，它有什么区别呢？在这里:

$seen-numbers{$n} = True;

$n将存储为 Int ，其 .WHICH用于散列以获得 O(1) 查找。如果我们刚刚使用 {}相反，我们会有 Int被胁迫成 Str为 key 。这种差异在这里变得很重要:

return False if $n ∈ $seen-numbers;

因为集合成员运算符会寻找相同的值。所以当我们有一个对象哈希时，:{} ，存储 Int s，然后 $n可能与散列中的键之一相同；如果是，则算法终止。但是，使用普通散列，创建于 {} , 键是 Str ，因此永远不会与 Int 相同，因此集合成员检查将始终失败，从而导致算法不终止。

该计划与它自己的决定是一致的。可以这样写:

return False if $seen-numbers{$n}:exists;

然后它将与 {} 一起使用( Hash ) 也是。但是，它会将数字强制转换为 Str用于每次存储和查找，使用 :{} 避免了成本.因此，我们可以说程序通过使用 :{} 做出了更高效的数据结构选择。 ，这反过来又启用了 ∈ ，这可能被认为更具可读性(特别是如果目标受众是习惯阅读此类数学运算符的人)。

编写程序的另一种可能更清晰的方法是:

my %seen-numbers is SetHash;
while $n > 1 {
    return False if $n ∈ %seen-numbers;
    %seen-numbers{$n} = True;
    $n = $n.comb.map(*²).sum
}
return True;

这更清楚地表明我们正在考虑 %seen-numbers作为一个集合，尽管在这种情况下，名称对其用途的疑问相对较少。