performance - 编写无限列表以跳过 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..] \\ ...

在这种情况下，您必须使用 Daniel Fischer 的回答中提到的 minus 依次删除它们。这里没有 Elixir 。

但是 there's also a union ，上面变成了

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

优点是，我们可以 arrange the unions in a tree ，并获得算法改进。