Haskell оптимизация списка понимание

Question

У меня есть кусок кода, написанного для проекта Эйлер

primes :: [Integer] 
primes = filter isPrime [2..] 
    where isPrime n = not $ any (\x -> n `mod` x == 0) [2..n-1] 

ans = max [x | x <- primes, 600851475143 `mod` x == 0] 

Конечно, я не стал дожидаться его завершения. Но мне интересно, он когда-нибудь вернется? Я полагаю, это зависит от того, знает ли haskell, чтобы остановиться на 600851475143?

Answer 1

Нет, это никогда не вернется. Haskell имеет нестрогую семантику, поэтому для совместимой реализации не нужно оценивать части неиспользуемого выражения; Однако это не доказательство теоремы. Система времени выполнения не пытается доказать, что в вашем списке не может быть большего количества. Вместо этого, когда ваше выражение оценивается maxбудет, чтобы посмотреть на каждый элемент в вашем списке, чтобы определить его максимальное значение. Это будет проблемой, потому что согласно тому, что я сказал выше, ваш список никогда не может быть определен, чтобы быть выполненным (поскольку список источников бесконечен, всегда есть больше элементов, которые потенциально включены в ваше выражение списка).

Вам нужно заполнить takeWhile, а затем filter до вашего макс.

Кроме того, мне, вероятно, не нужно указывать это, но ваш метод primes невероятно неэффективен и займет на самом деле долгое время, чтобы генерировать числа так высоко, как вам кажется, что нужно для этой проблемы.