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

Я новичок в Haskell и пытаюсь реализовать решето Эйлера в стиле потоковой обработки.

Когда я проверилHaskell wiki о простых числах , я нашел какой-то таинственный метод оптимизации потоков. В 3.8 линейное слияние этой Вики: 

primesLME = 2 : ([3,5..] `minus` joinL [[p*p, p*p+2*p..] | p <- primes']) 
  where
    primes' = 3 : ([5,7..] `minus` joinL [[p*p, p*p+2*p..] | p <- primes'])

joinL ((x:xs):t) = x : union xs (joinL t)

И он говорит

"подача двойных простых чисел введена здесь, чтобы предотвратить ненужное запоминание и, таким образом, предотвращение утечки памяти, согласно Мелиссе О'Нил. код. "

Как это может быть? Я не могу понять, как это работает.

1 8
haskell primes

1 ответ:

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

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, р = {2} U ({3,4,...} \ U {{Р2, Р2+Р, Р2+2p , ...} / p in 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)

На самом деле, при тестировании в Ideon, он показывает практически постоянное потребление памяти.

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

Исходными определениями являются: 

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..]
Оба они очень неэффективны из-за преждевременного обращения с кратными числами. Легко исправить первый определение путем слияния 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) используется здесь как без точек стенография.)

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

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

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

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..]
9