list - 有没有一种偷懒的方式来编写减号功能(从列表中删除项目)？

我的函数看起来像这样:

minus :: (Eq a) => [a] -> [a] -> [a]
minus [] xs                      = []
minus (y:ys) xs | y `notElem` xs = y : (minus ys xs)
                | otherwise      = minus ys xs

可以这样使用:

[99,44,55,22,23423] `minus` [55,22]

输出:[99,44,23423]
我写这篇文章是因为我正在研究Euler项目问题​​7，而Eratosthenes筛子似乎是正确的工具，虽然它是正确的工具，但我一直读着Wikipedia page并继续阅读有关Euler筛子的部分。

我试图复制/粘贴代码并在GHCi中运行它，但是我的GHCi版本没有名为Data.OrdList的模块，而且在Hoogle中找不到名为minus的函数。

这是来自维基百科的代码:

 import Data.OrdList (minus)

 primes = euler [2..]
 euler (p : xs) = p : euler (xs `minus` map (*p) (p : xs))

如果在其中替换我的减号函数，则会出现内存不足错误，因为我的函数不是惰性的。

有没有办法使懒惰的负函数起作用？

我的减号功能与Wikipedia文章中的减号功能是否相同？

最佳答案

正如sepp2k所指出的，minus的实现必须采用有序列表。这里有一个可能的实现:

minus :: Ord a => [a] -> [a] -> [a]
minus [] _ = []
minus xs [] = xs
minus l1@(x:xs) l2@(y:ys)
    | x > y = minus l1 ys
    | x < y = x : minus xs l2
    | otherwise = minus xs l2