是否有一种懒惰的方式来编写减号函数(从列表中删除项目)？

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的Sieve似乎是正确的工具,而且它是,但我一直在阅读维基百科页面并得到关于Euler筛子的部分.

我试图复制/粘贴代码并在GHCi中运行它,但我的GHCi版本没有名为Data.OrdList的模块,我找不到minusHoogle中调用的函数.

这是维基百科的代码:

 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

Answer 2

有没有办法做一个懒惰的减号功能？

如果您不假设输入列表是有序的(并且您不允许对它们进行排序),则不会.在知道结果的第一个元素之前,您需要知道list1的第一个元素是否在list2中.因此,在最坏的情况下生成单个元素之前,您无法绕过必须评估整个第二个列表.

但是,如果您假设输入列表是有序的(维基百科使用的减号显然是因为模块被称为*Ord*List),那么编写一个足够懒惰的减函数是非常容易的.

由于您的输入列表实际上是有序的,因此这样的减号功能可以完美地满足您的需求.