写无限列表跳过p的每个因素？

Question

我怎样才能有效地代表清单[0..] \\ [t+0*p, t+1*p ..]？

我已经定义:

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

我想高效地表示无限的名单是的差异[0..]和factors p t,而是使用\\从Data.List需要甚至中型列出了太多的记忆:

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

我知道我可以代表之间的值t+0*p,并t+1*p用:

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

但是,反复计算和连接innerList增加间隔似乎很笨拙.

我能否有效地表示[0..] \\ (factors p t)不计算rem或mod每个元素？

Answer 1

对于无限列表[0..] \\ [t,t+p..],

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

当然,如果您想要删除其他一些因素,例如,这种方法根本无法扩展

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

在这种情况下,你必须按顺序删除它们minus,在Daniel Fischer的回答中提到.这里没有灵丹妙药.

但也有一个union,上面变成了

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

优点是,我们可以将工会安排在树中,并进行算法改进.