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 

편집

아차는! 문제가 아니었다. 다음 버전의 알고리즘 (아래)에서 나는 !!의 사용을 제거했습니다; 또한, 나는 @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 고정 : 배열을 사용하려면이 알고리즘을 변형하는 방법

1 .- 목록 대신? (하스켈에서 상태와 배열을 다루는 법을 배우기위한 것입니다.) 누군가 이미 코멘트에 답변했지만,별로 좋지 않은 설명이있는 예를 가리키고 있습니다.

2.- 새로운 소수가 발견 될 때마다 목록의 연결을 제거하는 방법은 무엇입니까?

진정한 ->은 [전류]

Answer 1

여기에 귀하의 코드를 더 많거나 적은 직접 번역 정수의 언 박싱 배열 작업에있어 ++ primesAcum :

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는 키가 corecursive 생각에 재귀 적 사고로 전환하는 것입니다

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

입니다 의미론은 나머지를 처리합니다.