Writing infinite list to skip every factor of p?
arithmetic-expressions, functional-programming, haskell, math, performance
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.
Problem
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?