Как уже говорили другие, вы почти наверняка не хотите использовать блок do в своем коде, где вы это делаете. do предназначен для Monads и его следует избегать при изучении Haskell, и, вероятно, он неуместен, поскольку единственное Monad здесь - [], которое игнорирует любое определение innerSieve. Код на Haskell описывает значения и типы в терминах других значений и типов. Программы на Haskell не говорят компьютеру, что делать, они говорят ему, что является . Это радикальный способ мышления, но очень мощный. do нотация - это специальный синтаксис для обработки монад, представляющих собой особый вид значений, которые можно использовать для чистого и эффективного кодирования вычислений (включая императивные вычисления и переходы состояний), но для хорошего использования требуется широкое понимание языка Haskell.
Мой совет новичкам на Haskell: «Избегайте монад и нотаций do до тех пор, пока вы не освоите: рекурсию, функции высшего порядка и классы типов. Вам не нужно do для тестирования ваших программ (используйте GHCi), поэтому изучите реальное функциональный образ мышления. Попробуйте программировать так, чтобы ваши программы ничего не делали! "
Итак, как бы вы пошли писать сито с Эратосфеном на Хаскеле? Есть много элегантных способов. Предупреждение: спойлеры впереди. Если вы хотите сделать это самостоятельно, перестаньте читать
Вы прокомментировали:
innerSieve n i j = [x | x <- [i..n], x `mod` j == 0]
Я не уверен, какой смысл n и i здесь. Было бы более элегантно написать
innerSieve j ls = [x | x <- ls, x `mod` j == 0]
который имеет тип
innerSieve :: Integral x => x -> [x] -> [x]
поэтому, другими словами, он принимает список значений некоторого типа x, так что этот тип может обрабатываться как целое число, и возвращает все целые кратные исходного значения.
Вы могли бы использовать это, чтобы написать сито Эратосфена, но лучшим способом было бы получить все значения, которые не кратны. Причина в том, что тогда вы можете просто сложить их вместе, чтобы получить ваше полное простое сито
innerSieve j ls = [x | x <- ls, x `mod` j /= 0]
Здесь /= - это способ сказать Хаскеллу «не равный». Круто, так что давайте построим простое сито из этого
sieve (x:xs) = x : sieve (innerSieve x xs)
sieve [] = []
Что это говорит? ну, он берет список чисел и возвращает вам новый список, состоящий из первого из этих чисел, и сито применяется к остальным этим числам, за исключением тех, которые кратны первому. (x:xs) является шаблоном , который соответствует любому списку, кроме пустого списка, связывая x с заголовком списка и xs с хвостом списка. [] - это шаблон, который соответствует любому пустому списку.
Наконец, вы можете определить бесконечный список всех простых чисел
primes = sieve [2..]
Выражение [2..] создает список 2,3,4,5,6,7,etc, который продолжается вечно. Выглядит страшно (бесконечные списки), но ничего страшного из-за прославленной ленивой оценки Хаскелла. Чтобы получить n-е простое число, вы можете сказать:
nthPrime n = primes !! (n - 1)
, который просто индексируется в списке простых чисел. Haskell вычислит только минимум, необходимый для возврата результата, поэтому эта функция завершится, даже если primes бесконечно долго
или получить все простые числа до числа
primesUpToN n = take n primes
Итак, вся ваша кодовая база в конечном итоге будет:
sieve [] = []
sieve (x:xs) = x : sieve (innerSieve x xs) where
innerSieve j ls = [x | x <- ls, x `mod` j /= 0]
primes = sieve [2..]
nthPrime n = primes !! (n - 1)
primesUpToN n = take n primes
На самом деле это не сито Эратосфена, так как вы не «помечаете» ценности. Но на самом деле это сито «лучше», поскольку оно и быстрее, и определяет набор всех простых чисел, а не число с числом простых чисел. Это не то, как вы должны заниматься генерацией простых чисел, но в 6 строках кода (большинство из которых не нужны) трудно утверждать, что мутация или циклы делают вещи проще.