list - 有没有一种懒惰的方法来编写减号函数(从列表中删除项目)？

Question

我的功能如下所示:

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]
我写这篇文章是因为我正在研究 Project Euler 问题 7，Eratosthenes 筛似乎是正确的工具，而且确实如此，但我一直在阅读 Wikipedia page并谈到了欧拉的筛子。

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

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

 import Data.OrdList (minus)

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

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

有没有办法制作一个惰性减法函数？

我的减号功能是否与维基百科文章中的减号功能相同？

Answer 1

正如 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