Почему: {} создает объект "Hash [Mu, Any]" (и что это такое и как он сравнивается с обычным "Hash")?

Сначала я просто удивился, почему перед пустыми скобками в строке 2 этого кода стоит двоеточие (из Perl 6 Advent Calendar, 25 декабря 2018 г.)?

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) связывает процессор в течение нескольких минут (пока я не завершил процесс). Также, в этом случае, say $seen-numbers.^name; печатает Hash.

Итак, очевидно :{} приводит к созданию Hash[Mu,Any]. Как это работает? Это обходной путь или идиоматизм? А что такое Hash[Mu,Any] и как он сравнивается с обычным Hash?

Ответы

Ответ 1

Hash имеет ключи Str. Любой ключ, который не является Str будет приведен к одному перед сохранением значения под этим строковым ключом. {} Создает пустой Hash.

Это поведение можно изменить, Hash аргументы типа Hash. Например, Hash[Int] по-прежнему имеет строковый ключ с автоматическим приведением, но может хранить только значения Int (так же, как Array[Int] может хранить только значения Int). Также можно передать аргумент второго типа, чтобы выбрать тип ключа. Это создает то, что часто называют "хешем объекта", и в нем хранятся точные ключи, предоставленные в индексаторе. Так 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;

Потому что оператор набора членства ищет значения одинаковыми. Поэтому, когда у нас есть хеш объекта :{}, хранящий Int, тогда $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 как о наборе, хотя в этом случае имя оставляет относительно небольшой вопрос о его назначении.