двойной поток для предотвращения ненужной мемоизации?

Обычно определение потока простых чисел в формулировке сита Эратосфена Ричардом Бердом является самодостаточным:

import Data.List.Ordered (minus, union, unionAll)

ps = ((2:) . minus [3..] . foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r) []) ps

Простые числа ps, полученные этим определением, используются как входные для него. Чтобы предотвратить порочный круг, определение заполняется начальным значением 2. Это соответствует математическому определению решета Эратосфена как нахождение простых чисел в промежутках между композитами, пронумерованных для каждого простого числа p путем подсчета с шагом p, P = {2} U ({3,4, ... } \ U {{p ², p ² + p, p ² + 2p, ...} | p в P}).

Созданный поток используется как вход в его собственном определении. Это вызывает сохранение в памяти всего потока простых чисел (или большей его части). Исправление здесь - совместное использование, corecursive:

fix f  = xs where xs = f xs                    -- a sharing fixpoint combinator
ps     = fix ((2:) . minus [3..] . foldr (...) [])
    -- = xs where xs = 2 : minus [3..] (foldr (...) [] xs)

Идея (благодаря Мелиссе О'Нил) состоит в том, чтобы разделить это на два потока, при этом внутренний цикл перейдет во второй поток простых чисел "над" ним:

fix2 f  = f xs where xs = f xs                 -- double-staged fixpoint combinator
ps2     = fix2 ((2:) . minus [3..] . foldr (...) [])
     -- = 2 : minus [3..] (foldr (...) [] xs) where
     --                                   xs = 2 : minus [3..] (foldr (...) [] xs)

Таким образом, когда ps2 производит какое-то простое число p, его внутренний поток xs "основных" простых чисел должен быть создан только до примерно sqrt p, а любые простые числа, созданные ps2, могут быть отброшены и собраны в мусор система сразу после этого:

    \
     \
      <- ps2 <-.
                \
                 \
                  <- xs <-.
                 /         \ 
                 \_________/ 

Простые числа, созданные внутренним циклом xs, не могут быть немедленно отброшены, потому что они необходимы для самого xs потока. Когда xs произвел простое число q, только его часть ниже sqrt q может быть отброшена сразу после того, как оно будет использовано foldr частью вычисления. Другими словами, эта последовательность поддерживает обратный указатель в себя вплоть до sqrt самого большого произведенного значения (поскольку оно потребляется его потребителем, например print).

Таким образом, с одним циклом подачи (с fix) почти вся последовательность должна быть сохранена в памяти, в то время как с двойной подачей (с fix2) в основном должен сохраняться только внутренний цикл, который достигает только квадратного корня из текущего ценность, произведенная основным потоком. Таким образом, общая сложность пространства снижается примерно с O (N) до примерно O (sqrt (N)) - резкое сокращение.

Чтобы это работало, код должен быть скомпилирован с оптимизацией, то есть с переключателем -O2, и работать автономно. Возможно, вам также придется использовать переключатель -fno-cse. И в коде тестирования должна быть только одна ссылка на ps2:

main = getLine >>= (read >>> (+(-1)) >>> (`drop` ps2) >>> print . take 5)

Фактически, при тестировании в Ideone, он действительно показывает практически постоянное потребление памяти.

И это решето Эратосфена, а не решето Эйлера.

Исходные определения:

eratos (x:xs) = x : eratos (minus xs $ map (*x) [x..] )    -- ps = eratos [2..]
eulers (x:xs) = x : eulers (minus xs $ map (*x) (x:xs))    -- ps = eulers [2..]

Оба они очень неэффективны из-за преждевременной обработки кратных. Легко исправить определение first, объединив map и перечисление в одно удаленное перечисление (с x на x*x, т. Е. [x*x, x*x+x..]), так что его обработка может быть отложено - потому что здесь кратные каждому простому числу генерируются независимо (перечисляются через фиксированные интервалы):

eratos (p:ps) xs | (h,t) <- span (< p*p) xs =                 -- ps = 2 : eratos ps [2..]
                    h ++ eratos ps (minus t [p*p, p*p+p..])   -- "postponed sieve"

который совпадает с ситом Птицы в верхней части этого сообщения, по сегментам:

ps = 2 : [n | (r:q:_, px) <- (zip . tails . (2:) . map (^2) <*> inits) ps,
              n           <- [r+1..q-1] `minus` foldr union [] 
                               [[s+p, s+2*p..q-1] | p <- px, let s = r`div`p*p]]

((f <*> g) x = f x (g x) используется здесь как сокращение pointfree.)

Для второго определения, т. Е. eulers, нет простого решения.

дополнение: вы можете увидеть ту же идею, реализованную с помощью генераторов Python, для сравнения здесь.

Фактически, этот код Python использует телескопическое, многоступенчатое рекурсивное создание потоков эфемерных простых чисел; в Haskell мы можем организовать это с помощью многоэтапного комбинатора фиксированных точек без совместного использования ресурсов _33 _ :

primes = 2 : _Y ((3:) . sieve 5 . unionAll . map (\p -> [p*p, p*p+2*p..]))
  where
    _Y g = g (_Y g)                                   -- == g . g . g . g . ....

    sieve k s@(x:xs) | k < x = k : sieve (k+2) s      -- == [k,k+2..] \\ s,
                     | True  =     sieve (k+2) xs     --    when s ⊂ [k,k+2..]