Geek asks and answers

Why wouldn't my sieve end when I rewrote it as a crease?

What is the specific issue with mine foldlthat is preventing the completion or release of the output?

First I got a sieve for primes. This is not the best, but it works just fine like (for example) take 20 primesA.

primesA :: [Integer]
primesA = sieve 2 []

sieve :: Integral a => a -> [a] -> [a]
sieve i []   = (i:) $ sieve (i + 1) $ map (*i) [i ..]
sieve i composites@(h : t)
  | i == h    =     sieve (i + 1) t
  | otherwise = (i:) $ sieve (i + 1) $ unionIncreasing composites $ map (*i) [i ..]

unionIncreasing :: Ord a => [a] -> [a] -> [a]
unionIncreasing [] b = b
unionIncreasing a [] = a
unionIncreasing a@(ah:at) b@(bh:bt) | ah <  bh  = ah : at `unionIncreasing` b
                                    | ah == bh  = ah : at `unionIncreasing` bt
                                    | otherwise = bh : a  `unionIncreasing` bt

Then I thought that it would be more Haskell-y to eliminate the counter iusing foldlas follows. But it is not effective.

primesB :: [Integer]
primesB = [2..] `differenceIncreasing` composites

composites :: [Integer]
composites = foldl f [] [2..]
  where f [] i = map (*i) [i ..]
        f knownComposites@(h:t) i | i == h    = knownComposites
                                  | otherwise = (h:) $ unionIncreasing t $ map (*i) [i ..]

differenceIncreasing :: Ord a => [a] -> [a] -> [a]
differenceIncreasing [] b = []
differenceIncreasing a [] = a
differenceIncreasing (x:xs) (y:ys) | x <  y    = x : xs `differenceIncreasing` (y:ys)
                                   | x == y    = xs `differenceIncreasing` ys
                                   | otherwise = (x:xs) `differenceIncreasing` ys

It does not complete and does not display any results at startup (for example) head primesB.

Presumably ghci looks at an infinite number of lists of multiple primes in his futile attempt to achieve the meaning of the head of the list.

But why specifically does this?

+5
source share
3

foldl . :

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

, Haskell, thunk, , , (, ). foldl , []. , ( ):

foldl (flip (:)) [] [1..]
  = foldl (flip (:)) [1] [2..]
  = foldl (flip (:)) [2, 1] [3..]
  = foldl (flip (:)) [3, 2, 1] [4..]
  = foldl (flip (:)) [4, 3, 2, 1] [5..]
  .
  .
  .

foldl , foldl , . , .

foldr , f :

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

:

foldr (:) [] [1..]
  = 1 : foldr (:) [] [2..]

(:) , ; - .

+11

(: https://cstheory.stackexchange.com/ , , .)

( 11 . '). , .

:

--     map (*i) [i ..] == map (*i) [i, i+1 ..] == [i*i, i*i+i ..]
--     sieve 2 [] where sieve i [] = (i:) $
--               sieve (i + 1) [i*i, i*i+i ..] == 2 : sieve 3 [4, 6 ..]

primesA :: [Integer]
primesA = 2 : sieve 3 [4, 6 ..]

sieve p cs@(c : t)
   | p == c    =     sieve (p + 1) t
   | otherwise = p : sieve (p + 1) (unionI cs [p*p, p*p+p ..])

unionI a@(x:xs) b@(y:ys) | x <  y    = x : xs `unionI` b
                         | x == y    = x : xs `unionI` ys
                         | otherwise = y : a  `unionI` ys

. (...(((a+b)+c)+d)+...), , .

. . 5, [25, 30 ..] . , 25. ( Θ(n) Θ(sqrt(n/log n)), n- ). .

, ( ps , , ):

primesAC = [2,3] ++ sieve 4 (tail primesAC) 9 [4,6..]

sieve k ps@(p:pt) q cs@(c:ct)                 -- candidate "k", prime "p"
  | k == c  =     sieve (k + 1) ps q ct       -- square "q", composite "c"
  | k < q   = k : sieve (k + 1) ps q cs
  | otherwise =   sieve k       pt (head pt^2)       -- k == q == p*p
                        (unionI cs [q, q+p ..])

Richard Bird, foldr, a+(b+(c+(...))), , :

primesAD = (2 :) . sieve 3 . 
            foldr (\p r-> p*p : unionI [p*p+p, p*p+2*p ..] r) [] $ primesAD

sieve p cs@(c : t)                  -- == diffI [p..] cs, if p<=c
  | p == c    =     sieve (p + 1) t
  | otherwise = p : sieve (p + 1) cs

, , .

So foldr, foldl, .

primesB :: [Integer]
primesB = [2..] `diffI` composites

composites = foldl f [4,6..] [3..]
  where 
        f cs@(h:t) i | i == h    = cs    
                     | otherwise = h : unionI t [i*i, i*i+i ..]

diffI (x:xs) (y:ys) | x <  y    = x : xs `diffI` (y:ys)
                    | x == y    =     xs `diffI` ys
                    | otherwise = (x:xs) `diffI` ys

, , composites , ; , foldl , ( ). foldl .:) iterate, . , , :

composites = foldl f [4,6..] [3..]
 -- no part of calculation of (f [4,6..] 3) is forced here, but if it were, ...
 = foldl f (f [4,6..] 3) [4..]                  
 = foldl f (4:unionI [6,8..] [9,12..]) [4..]    
 = foldl f (4:unionI [6,8..] [9,12..]) [5..]
 = foldl f (4:union (unionI [6,8..] [9,12..]) [25,30..]) [6..]
 = foldl f (4:union (union (unionI [6,8..] [9,12..]) [25,30..]) [36,42..]) [7..]
 = ....

([2..] `diffI`) sieve 2 , .

+2

, , primesB, . " ", cstheory.se. , , , , , . 11 ME O'Neill : http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf ( @Wes) : http://dx.doi.org/10.1017/S0956796808007004

primesB :: [Integer]
-- #1 necessary change
-- primesB = [2..] `differenceIncreasing` composites
primesB = 2 : [3..] `differenceIncreasing` composites

-- #2 necessary change, entire function
composites = foldr f [] primesB -- not foldl, not [2..]
  where f :: Integer -> [Integer] -> [Integer]
        -- no destructuring of knownComposites;
        -- square the first list element and don't put that in unionIncreasing second argument
        f i knownComposites = ((i*i):) $ unionIncreasing knownComposites $ map (*i) [(i+1)..]

-- No change needed in `unionIncreasing` and `differenceIncreasing`.

, , .

0

More articles:


All Articles