Как улучшить этот алгоритм с помощью 1) использовать массивы, 2) избежать конкатенации списков (ленивые списки?)?

Question

Я пытался узнать, как работает STArray, но я не мог. (Док бедрен или, по крайней мере, тот, который я нашел).

В любом случае, у меня есть следующий алгоритм, но он использует много!, Что медленно. Как я могу преобразовать его в использование монады STArray?

-- The Algorithm prints the primes present in [1 .. n] 

main :: IO() 
main = print $ primesUpTo 100 

type Nat = Int 

primesUpTo :: Nat -> [Nat] 
primesUpTo n = primesUpToAux n 2 [1] 

primesUpToAux :: Nat -> Nat -> [Nat] -> [Nat] 
primesUpToAux n current primes = 
    if current > n 
    then primes 
    else primesUpToAux n (current + 1) newAcum 
    where newAcum = case isPrime current primes of 
        True -> primes++[current] 
        False -> primes 

isPrime :: Nat -> [Nat] -> Bool 
isPrime 1 _ = True 
isPrime 2 _ = True 
isPrime x neededPrimes = isPrimeAux x neededPrimes 1 

isPrimeAux x neededPrimes currentPrimeIndex = 
    if sqrtOfX < currentPrime 
    then True 
    else if mod x currentPrime == 0 
     then False 
     else isPrimeAux x neededPrimes (currentPrimeIndex + 1) 
    where 
     sqrtOfX = sqrtNat x 
     currentPrime = neededPrimes !! currentPrimeIndex 

sqrtNat :: Nat -> Nat 
sqrtNat = floor . sqrt . fromIntegral 

Редактировать

К сожалению, !! это не проблема; в следующей версии алгоритма (ниже) я удалил использование !!; Кроме того, я установил 1 является простым, что это не так, как указано на @pedrorodrigues

main :: IO() 
main = print $ primesUpTo 20000 

type Nat = Int 

primesUpTo :: Nat -> [Nat] 
primesUpTo n = primesUpToAux n 1 [] 

primesUpToAux :: Nat -> Nat -> [Nat] -> [Nat] 
primesUpToAux n current primesAcum = 
    if current > n 
    then primesAcum 
    else primesUpToAux n (current + 1) newPrimesAcum 
    where newPrimesAcum = case isPrime current primesAcum of 
          True -> primesAcum++[current] 
          False -> primesAcum 

isPrime :: Nat -> [Nat] -> Bool 
isPrime 1 _ = False 
isPrime 2 _ = True 
isPrime x neededPrimes = 
    if sqrtOfX < currentPrime 
    then True 
    else if mod x currentPrime == 0 
     then False 
     else isPrime x restOfPrimes 
    where 
      sqrtOfX = sqrtNat x 
      currentPrime:restOfPrimes = neededPrimes 

sqrtNat :: Nat -> Nat 
sqrtNat = floor . sqrt . fromIntegral 

Сейчас этот вопрос находится около 2 вопросов на самом деле:

1.- Как преобразовать этот алгоритм для использования массивов вместо списков? (Ради понимания того, как обрабатывать состояние и массивы в Haskell) Кто-то уже ответил в комментариях, но указывает на не очень хороший объясненный пример.

2.- Как устранить конкатенацию списков каждый раз, когда найден новый штрих?

True -> primesAcum ++ [Текущее]

Answer 1

Вот более или менее прямой перевод кода в работе с Unboxed массив целых чисел:

import Control.Monad 
import Control.Monad.ST 
import Data.Array.ST 
import Data.Array.Unboxed 
import Control.Arrow 

main :: IO() 
main = print . (length &&& last) . primesUpTo $ 1299709 

primesUpTo :: Int -> [Int] 
primesUpTo = takeWhile (> 0) . elems . primesUpToUA 

primesUpToUA :: Int -> UArray Int Int 
primesUpToUA n = runSTUArray $ do 
    let k = floor(1.25506 * fromIntegral n/log (fromIntegral n)) -- WP formula 
    ar <- newArray (0,k+1) 0   -- all zeroes initially, two extra spaces 
    let 
    loop c i | c > n = return ar   -- upper limit is reached 
      | otherwise = do    -- `i` primes currently in the array 
     b <- isPrime 0 i c    -- is `c` a prime? 
     if b then do { writeArray ar i c ; loop (c+1) (i+1) } 
     else loop (c+1) i 
    isPrime j i c | j >= i = return True -- `i` primes 
        | otherwise = do   -- currently in the array 
      p <- readArray ar j 
      if p*p > c   then return True 
      else if rem c p == 0 then return False 
      else     isPrime (j+1) i c 
    loop 2 0 

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

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

Конечно, вы можете переписать свой код на основе списков, чтобы вести себя лучше; the simplest re-write является

ps :: [Int] 
ps = 2 : [i | i <- [3..], 
       and [rem i p > 0 | p <- takeWhile ((<=i).(^2)) ps]] 
primesTo n = takeWhile (<= n) ps 

Ключ, чтобы перейти от рекурсивного мышления к corecursive мышления - не , как добавить в конце, явно, но определить, как список будет производиться — и пусть ленивых семантика позаботится об остальном.