Writing infinite list to skip every factor of p?

StackOverflow https://stackoverflow.com/questions/18320391

Question

How can I efficiently represent the list [0..] \\ [t+0*p, t+1*p ..]?

I have defined:

Prelude> let factors p t = [t+0*p, t+1*p ..]

I want to efficiently represent an infinite list that is the difference of [0..] and factors p t, but using \\ from Data.List requires too much memory for even medium-sized lists:

Prelude Data.List> [0..10000] \\ (factors 5 0)
<interactive>: out of memory

I know that I can represent the values between t+0*p and t+1*p with:

Prelude> let innerList p1 p2 t = [t+p1+1, t+p1+2 .. t+p2-1]
Prelude> innerList 0 5 0
[1,2,3,4]

However, repeatedly calculating and concatenating innerList for increasing intervals seems clumsy.

Can I efficiently represent [0..] \\ (factors p t) without calculating rem or mod for each element?

Was it helpful?

Solution

For the infinite list [0..] \\ [t,t+p..],

yourlist t p = [0..t-1] ++ [i | m <- [0,p..], i <- [t+m+1..t+m+p-1]]

Of course this approach doesn't scale, at all, if you'd want to remove some other factors, like

[0..] \\ [t,t+p..] \\ [s,s+q..] \\ ...

in which case you'll have to remove them in sequence with minus, mentioned in Daniel Fischer's answer. There is no magic bullet here.

But there's also a union, with which the above becomes

[0..] \\ ( [t,t+p..] `union` [s,s+q..] `union` ... )

the advantage is, we can arrange the unions in a tree, and get algorithmic improvement.

OTHER TIPS

You can't use (\\) for that, because

(\\)                    :: (Eq a) => [a] -> [a] -> [a]
(\\)                    =  foldl (flip delete)

the list of elements you want to remove is infinite, and a left fold never terminates when the list it folds over is infinite.

If you rather want to use something already written than write it yourself, you can use minus from the data-ordlist package.

The performance should be adequate.

Otherwise,

minus :: Ord a => [a] -> [a] -> [a]
minus xxs@(x:xs) yys@(y:ys)
    | x < y     = x : minus xs yys
    | x == y    = minus xs ys
    | otherwise = minus xss ys
minus xs _      = xs

You can use a list comprehesion with a predicate, using rem:

>>> let t = 0
>>> let p = 5
>>> take 40 $ [ x | x <- [1..], x `rem` p /= t ]
[1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24,26,27,28,29,31,32,33,34,36,37,38,39,41,42,43,44,46,47,48,49]

If you want efficiency, why does your solution have to use list comprehension syntax?

Why not something like this?

 gen' n i p | i == p = gen' (n + p) 1 p
 gen' n i p = (n+i) : gen' n (i+1) p
 gen = gen' 0 1

and then do

 gen 5

Because you have ascending lists, you can simply lazily merge them:

 nums = [1..]
 nogos = factors p t
 result = merge nums (dropWhile (<head nums) nogos) where
      merge (a:as) (b:bs)
        | a < b = a : merge as (b:bs)
        | a == b = merge as bs
        | otherwise = error "should not happen"

Writing this in a general way so that we have a function that builds the difference of two infinite lists, provided only that they are in ascending order, is left as exercise. In the end, the following should be possible

 [1..] `infiniteDifference` primes `infiniteDifference` squares

For this, make it a left associative operator.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top