4

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

我已经定义：

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

我想有效地表示一个无限列表，它是 和 的区别[0..]，factors p t但使用\\fromData.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每个元素的情况下有效地表示吗？

4

5 回答 5

7

对于无限列表[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` ... )

优点是，我们可以将联合排列成一棵树，并获得算法改进。

于 2013-08-19T19:00:54.327 回答
3

你不能用(\\)那个，因为

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

您要删除的元素列表是无限的，当它折叠的列表是无限的时，左折叠永远不会终止。

如果你宁愿使用已经写好的东西而不是自己写，你可以使用data-ordlist包中的减号。

性能应该是足够的。

否则，

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
于 2013-08-19T19:01:49.870 回答
1

您可以使用带有谓词的列表综合，使用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]
于 2013-08-19T18:22:52.473 回答
1

因为你有升序列表，你可以简单地懒惰地合并它们：

 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"

以一般方式编写此代码，以便我们有一个构建两个无限列表差异的函数，前提是它们按升序排列，留作练习。最后，以下应该是可能的

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

为此，将其设为左结合运算符。

于 2013-08-20T08:37:42.503 回答
1

如果您想要效率，为什么您的解决方案必须使用列表理解语法？

为什么不这样呢？

 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

然后做

 gen 5
于 2013-08-19T18:47:00.280 回答