Понимание ограничений ленивой оценки (сито эратосфена)

Question

В статье на Haskell Wiki о простых числах описывается следующая реализация сита Эратосфена:

primes = 2 : 3 : minus [5,7..] (unionAll [[p*p, p*p+2*p..] | p <- tail primes])

При выполнении ...

primes !! 2

... как Хаскелл распознает в этой конкретной ситуации, что он не пытается попробовать все p в хвосте primes (он же [3..]), а вместо этого делает только минус с 3?

Другими словами: откуда Хаскель узнает, что любой из других p (или их кратных) не будет совпадать с 5, что является возможным ответом.Есть ли хорошее эмпирическое правило, чтобы знать, когда компилятор достаточно умен, чтобы обрабатывать бесконечные случаи?

Answer 1

Собственно, суть в реализации unionAll.minus просто извлекает элементы из своего правильного аргумента один за другим, не подозревая (конечно, предполагается, что оба аргумента не уменьшаются).

Во-первых, давайте переписать его как

primes = 2 : ps 
ps     = 3 : t
t      = minus [5,7..] (unionAll [[p*p, p*p+2*p..] | p <- ps])

-- primes !! 2 == ps !! 1 == head t

       = minus [5,7..] (unionAll [[p*p, p*p+2*p..] | p <- (3 : t)])
       = minus [5,7..] (unionAll ([9, 15..] : [[p*p, p*p+2*p..] | p <- t]))

Теперь unionAll умный: он опирается на предположение (здесь факт), что в unionAll xs он утверждает, что (map head xs) неубывающий.

Как таковой, он знает он не должен сравнивать 9 ни с чем!Таким образом, он просто производит его безоговорочно (вы можете проверить его определение, чтобы проверить это самостоятельно):

       = minus [5,7..] 
               (9 : union [15, 21..] (unionAll ........))

Таким образом, minus имеет что-то для сравнения 5 и 7 с, и производит:

       = 5 : 7 : minus [9,11..] 
                       (9 : union [15, 21..] (unionAll ........))

Все это от знания только первого нечетного простого числа, 3.

Answer 2

(!!) требует только того, чтобы primes было оценено достаточно, чтобы выяснить, что есть как минимум 3 элемента и что такое третий элемент.Чтобы получить этот третий элемент, нам нужно начать оценку вызова minus.

minus, предполагая, что оба его аргумента отсортированы.Это описано в документации и выполняется в определении primes.Первое сравнение minus выполняется между 5 и 9, и это показывает, что 5 является первым элементом результата.В определении минус это случай LT -> x : loop xs (y:ys).

(!!) теперь имеет третий элемент primes, поэтому оценка не продолжается в primes или minus или unionAll.Эта перемотка между вычислением подвыражений и сопоставлением с шаблоном во внешних выражениях является ленивой оценкой.