Ленивые вычисления простых чисел в Haskell


Я хотел дать Хаскелл попробовать, и я начал с простого упражнения, которое я нашел здесь.

  1. Написать интерфейс isprime :: целое число -> типа bool, которое определяет, является ли данная целое число-простое.
  2. Определение простых чисел :: [целое число], список всех простых чисел.
  3. Пересмотреть интерфейс isprime , так что это только тесты делимости на простые множители.

Мой ответ на вопрос 1

isPrime :: Integer -> Bool
isPrime v = let maxDiv = floor(sqrt (fromIntegral v))
            in all (\x -> (v `rem` x) /= 0) [2..maxDiv]

Это было легко, кроме явных числовых преобразований я имел трудное время, чтобы получить права.

Мой ответ на вопрос 2

primes = filter isPrime [0..]

Это было слишком легко.

Мой ответ на вопрос 3

Мне потребовалось несколько часов, чтобы ответить на этот вопрос. Я быстро понял, что интерфейс isprime может использовать значения уже вычислены в массиве простых чисел. Итак, моя первая попытка была :

isPrime :: Integer -> Bool
isPrime v | v < 2 = False
          | otherwise = all (\x -> (v `rem` x) /= 0) (takeWhile (<v) primes)

интерфейс isprime отлично работает при V=0 и V=1, но зависает навсегда для V>1. Ок, я понял : взаимная рекурсия создает бесконечный цикл, из-за takeWhile пытается получить доступ к праймы элемент, который еще не вычислен.

Одна вещь, я не понимаю, правда, почему праймы !! 0 и праймы !! 1 висеть вечно, тоже.

Я пробовал много подходов для замены этого (takeWhile ( выражение, что бы остановить до достижения еще не вычисленное значение. Я пришел к этому решению :

isPrime :: Integer -> Bool
isPrime v | v < 2 = False
          | v == 2 = True
          | otherwise = all (\x -> (v `rem` x) /= 0) (takeWhile' (\t -> t*t<=v) primes)

takeWhile' :: (a -> Bool) -> [a] -> [a]
takeWhile' p (x:xs) = if p x then x : takeWhile' p xs else [x]

Это решение работает. Но я должен был определить takeWhile' , которая работает так же, как takeWhile, но также включает в себя первых несовпадающих элементов.

Вот мои вопросы к вам :

ОК : почему праймы !! 0 и праймы !! 1 зависает при моей первой попытке ?

Дь : есть ли магические takeWhileOnlyForAlreadyComputedElements функция ? Или построить, что бы предотвратить бесконечный цикл этой взаимной рекурсии ?

КК : есть ли takeWhile' уже существует в stdlib ? Или, может быть, того же эффекта можно достичь более простым способом ?



1524
1
задан 7 сентября 2011 в 01:09 Источник Поделиться
Комментарии
1 ответ

Не ответ на ваши вопросы, а также коррекция для вашего первого, зацикливание попытка за 3 квартал:

Все становится намного проще, если вы изначально иметь по крайней мере одно простое число в списке. Вы могли убедиться в этом, отдельном случае в интерфейс isprime, но почему бы не схитрить немного, и добавить его прямо?

primes = 2 : filter isPrime [3..]

Затем вы можете использовать ваши решения за 1 квартал без особых изменений (я взял свобода убивать некоторые скобки и т. д.):

isPrime :: Integer -> Bool
isPrime v = let maxDiv = floor $ sqrt $ fromIntegral v
in all ((/= 0).(v `rem`)) $ takeWhile (<= maxDiv) primes

Однако, это не лучший способ создать список простых чисел. Прочитал прекрасную бумагу http://www.cs.hmc.edu/~в oneill/документы/сито-плд.формат PDF подробнее.

[Править]

Я забыл упомянуть http://www.haskell.org/haskellwiki/Prime_numbers много интересных приемов.

4
ответ дан 7 сентября 2011 в 07:09 Источник Поделиться