为什么:{}创建一个"Hash [Mu,Any]"对象(它是什么以及它与普通的"Hash"相比如何)？

Question

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

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

A Hash有Str钥匙.Str在将该值存储在该字符串键下之前,任何非a的键都将被强制转换为一个键.在{}构建一个空Hash.

可以通过提供Hash类型参数来更改此行为.Hash[Int]例如,A 仍然具有自动强制字符串键,但只能存储Int值(很像Array[Int]只能存储Int值).也可以传递第二个类型参数来选择键的类型.这会创建通常称为"对象哈希"的东西,并存储索引器中提供的确切键.所以a Hash[Mu,Any]是具有无约束值和Any密钥类型的哈希(几乎所有类型都属于Any,但除了Junction).在.WHICH关键的用于散列.

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

那么,它有什么不同呢？这里:

$seen-numbers{$n} = True;

的$n将被存储为Int,其.WHICH用于散列得到O(1)查找.如果我们只是使用了{},那么我们就会Int被强迫进入Str钥匙.这种差异在这里很重要:

return False if $n ? $seen-numbers;

因为set membership运算符查找值相同.因此,当我们有一个对象哈希时:{},存储Ints,那么$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视为一个集合,尽管在这种情况下,该名称对其目的留下的问题相对较少.