Тест Хаскелла

Question

Я новичок в Haskell, и я пытаюсь немного:

isPrime :: Integer->Bool
isPrime x = ([] == [y | y<-[2..floor (sqrt x)], mod x y == 0])

У меня есть несколько вопросов.

1. Почему, когда я пытаюсь загрузить.hs, WinHugs говорят: экземпляры (Floating Integer, RealFrac Integer) требуются для определения isPrime?
2. Когда интерпретатор находит один элемент в правильном наборе, он немедленно останавливается или вычисляет весь набор?Я думаю, вы понимаете, о чем я.

Извините за мой английский.

Answer 1

1) Проблема в том, что sqrt имеет тип (Floating a) => a -> a, но вы пытаетесь использовать Integer в качестве аргумента. Таким образом, вы должны сначала преобразовать ваше целое число в число с плавающей точкой, например, написав sqrt (fromIntegral x)

2) Я не вижу причин, по которым == не должно быть ленивым, но для тестирования пустой коллекции вы можете использовать функцию null (которая определенно ленива, поскольку она работает с бесконечными списками):

isPrime :: Integer->Bool
isPrime x = null [y | y<-[2..floor (sqrt (fromIntegral x))], x `mod` y == 0]

Но чтобы получить более идиоматическое решение, разбейте проблему на более мелкие подзадачи. Во-первых, нам нужен список всех элементов y с y * y <= x: </p>

takeWhile (\y ->  y*y <= x) [2..]

Тогда нам нужны только элементы, которые делят x:

filter (\y ->  x `mod`y == 0) (takeWhile (\y ->  y*y <= x) [2..])

Затем нам нужно проверить, пуст ли этот список:

isPrime x = null (filter (\y ->  x `mod`y == 0) (takeWhile (\y ->  y*y <= x) [2..]))

И если вам это не нравится, замените некоторые из паренов на $

isPrime x = null $ filter (\y ->  x `mod` y == 0) $ takeWhile (\y ->  y*y <= x) [2..]

Для большей ясности вы можете "отдать" лямбды на аутсорсинг:

isPrime x = null $ filter divisible $ takeWhile notTooBig [2..] where
     divisible y = x `mod`y == 0
     notTooBig y = y*y <= x

Вы можете сделать его почти "читабельным для человека", заменив нулевой $ filter на not $ any:

isPrime x = not $ any divisible $ takeWhile notTooBig [2..] where
     divisible y = x `mod`y == 0
     notTooBig y = y*y <= x

Answer 2

1. Поскольку sqrt имеет тип Floating a => a -> a.Это означает, что вход должен быть типа Floating, а выход будет того же типа.Другими словами, x должен иметь тип Floating.Однако вы объявили x типа Integer, который не является Floating.Кроме того, floor требуется тип RealFrac, поэтому x также должен быть таким.

   В сообщении об ошибке предлагается исправить это, указав тип Integer a Floating (определивэкземпляр Floating Integer (и то же самое для RealFrac).

   Конечно, в данном случае это неправильный подход. Скорее вам следует использовать fromIntegral для преобразования x в Real(который является экземпляром Floating и RealFrac), а затем присвойте его sqrt.

2. Да. Как только == увидит, что правый операнд имеетхотя бы один элемент, он знает, что он не равен [] и, следовательно, возвращает False.

   При этом null - более идиоматический способ проверить, является ли список пустым, чем [] ==.

Answer 3

Решение Landei отлично, однако, если вы хотите более эффективную реализацию, у нас есть (благодаря BMeph):

-- list of all primes
primes :: [Integer]
primes = sieve (2 : 3 : possible [1..]) where
     sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
     possible (x:xs) = 6*x-1 : 6*x+1 : possible xs

isPrime :: Integer -> Bool
isPrime n = shortCircuit || (not $ any divisible $ takeWhile inRangeOf primes) where
    shortCircuit = elem n [2,3] || (n < 25 && ((n-1) `mod` 6 == 0 || (n+1) `mod` 6 == 0))
    divisible y = n `mod` y == 0
    inRangeOf y = y * y <= n

«Эффективность» происходит от использования постоянных простых чисел. Улучшает поиск двумя способами:

1. Среда выполнения Haskell может кэшировать результаты, поэтому последующие вызовы не оцениваются
2. Устраняет диапазон чисел по логике обратите внимание, что значение sieve является просто рекурсивной таблицей, в которой говорится, что глава список прост, и добавляет его к нему. Для остальных списков, если нет другое значение уже в списке, который составляет число, то его также простое possible - список всех возможных простых чисел, так как все возможные простые числа находятся в форма 6 * к-1 или 6 * к-1, кроме 2 и 3 То же правило применяется и к shortCircuit, чтобы быстро выручить расчеты

Сноска Д.Ф.
Still Это все еще ужасно неэффективный способ найти простые числа. Не используйте пробное деление, если вам нужно простое число больше нескольких тысяч, используйте вместо этого сито. Есть несколько гораздо больше эффективных реализаций на hackage .

Answer 4

Относительно второй точки она останавливается, например:

[] == [x | x <- [1..]]

Возвращает False

Answer 5

1. Я думаю, что WinHugs должен импортировать модуль для Integer и т. Д. ... Попробуйте Int
2. Переводчик не будет ничего вычислять, пока вы не позвоните, например, isPrime 32 тогда оно будет лениво вычислять выражение.

PS Ваша реализация isPrime - не лучшая реализация!