Writing infinite list to skip every factor of p?

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?

Answer 1

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.