Как улучшить этот алгоритм: 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

Теперь этот вопрос о двух вопросах действительно:

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

2.- Как устранить объединение списков каждый раз, когда обнаруживается новое простое число?

True -> primesAcum ++ [текущий]

Answer 1

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

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

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

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

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

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

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