Создать бесконечный список в Haskell с IO

Question

EDITED!

Я пытаюсь написать алгоритм, который генерирует (бесконечный) список простых чисел Мерсена. У меня есть алгоритм (Rabin-Miller), который возвращает IO Bool, в зависимости от того, считает ли алгоритм число простым или нет. Этот алгоритм называется rabinMiller, и он принимает два аргумента: первый - Integer, который говорит что-то о безопасности списка, и второе число, которое мы отправляем на тест primality.

Я хочу индексировать список всех простых чисел (называемых простых чисел), и для каждого p в простых количествах, проверьте, считает ли rabinMiller, что 2^p - 1 является простым. Если это так, мы представляем 2^p - 1 в список.

То, что я сейчас это:

rbMersenneGen :: Integer -> IO(IO [Integer]) 
rbMersenneGen k = do return $ rbMersenneGens 0 k 

rbMersenneGens :: Int -> Integer -> IO [Integer] 
rbMersenneGens x k = 
    let n = primes!!x 
     m = (2^n) - 1 
    in do 
    prim <- rabinMiller k m 
    if prim then 
     m:rbMersenneGens (x + 1) k 
    else 
     rbMersenneGens (x + 1) k 

Но это на самом деле не работает, так как я не могу получить тип m:rbMersenneGens (x + 1) k правой. Я получаю ошибку, что m является Integer вместо [Integer], а затем типа всей m:rbMersenneGens (x + 1) k неправильно и создает другие ошибки

Answer 1

Ваши оригинальные типы в порядке; нам просто нужно немного изменить определение rbMersenneGens. Я собираюсь реорганизовать функцию немного.

rbMersenneGen :: Integer -> IO [Integer] 
rbMersenneGen k = rbMersenneGens 0 k 

rbMersenneGens :: Int -> Integer -> IO [Integer] 
rbMersenneGens x k = 
    let n = primes!!x 
     m = (2^n) - 1 
    in do 
     prim <- rabinMiller k m 
     -- We call rmMersenneGens the same way in either case; 
     -- the only difference is which function we apply to the result 
     (if prim then (m:) else id) (rbMersenneGens (x+1) k) 

Ваша проблема заключается в том, что prim должна быть Bool для выражения if-else, и выражение do необходимо оценить до IO [Integer] значения. Это означает, что rabinMiller нужно будет вернуть значение [Bool] вместо IO Bool, что и есть. Исправление состоит в том, чтобы заменить if еще на Data.Bool.bool :: a -> a -> Bool -> a.

Это не тип проверки ...

rbMersenneGens :: Int -> Integer -> IO [Integer] 
rbMersenneGens x k = 
    let n = primes!!x 
     m = (2^n) - 1 
     prim = rabinMiller k m -- IO Bool 
    in (bool id (m:) prim) (rbMersenneGens (x+1) k) 

, потому что мы все еще пытаются лечить prim как Bool, а не IO Bool, но это делает:

rbMersenneGens :: Int -> Integer -> IO [Integer] 
rbMersenneGens x k = 
    let n = primes!!x 
     m = (2^n) - 1 
     prim = rabinMiller k m 
    in (bool id (m:)) <$> prim <*> (rbMersenneGens (x+1) k) 

Мы можем» т сделать if работы с IO Bool, но мы может лифт bool для работы с одним. На самом деле нам нужно только обрабатывать IO как Applicative, а не Monad. Мы заменяем >>= на fmap (в его инфиксной форме <$>).

Answer 2

У вас есть блок сделать в rbMersenneGens. Результат блока do всегда находится в той же монаде, что и внутри. Поскольку вы звоните rabinMiller внутри, который находится в монаде IO, результат блока do находится в монаде IO. Однако вы заявили, что rbMersenneGens возвращает [Integer], который не соответствует выведенному типу.