is there a lazy way to write the minus function (remove items from a list)?

Question

My function looks like this:

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

It can be used like this:

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

with output: [99,44,23423]

I wrote this because I'm looking at Project Euler problem 7, and the Sieve of Eratosthenes seems like the right tool, and it was, but I kept reading down the Wikipedia page and got to the part about Euler's sieve.

I tried to copy/paste the code and run it in GHCi, but my version of GHCi doesn't have a module called Data.OrdList, and I couldn't find a function called minus in Hoogle.

This is the code from Wikipedia:

 import Data.OrdList (minus)

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

If I substitute my minus function in there, I get an out of memory error, because my function isn't lazy.

Is there a way to make a lazy minus function?

Does my minus function do the same as the minus function in the Wikipedia article?

Answer 1

Is there a way to make a lazy minus function?

If you don't assume that the input lists are ordered (and you're not allowed to sort them), there isn't. You'll need to know whether the first element of list1 is in list2 before you know what the first element of the result will be. So you can't get around having to evaluate the whole second list before producing a single element in the worst case.

However if you assume that the input lists are ordered (which the minus used by wikipedia clearly does as the module is called *Ord*List), it is very easy to write a minus function that is sufficiently lazy.

And since your input list is in fact ordered, such a minus function would work perfectly for your needs.

Answer 2

As sepp2k pointed out, the implementation of minus must assume ordered lists. Here goes a possible implementation:

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 3

Google outperformed Hoogle.

Taken from http://hackage.haskell.org/packages/archive/data-ordlist/0.0.1/doc/html/src/Data-OrdList.html

minus :: (Ord a) => [a] -> [a] -> [a]
minus = minusBy compare

minusBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
minusBy cmp = loop
  where
     loop [] _ys = []
     loop xs [] = xs
     loop (x:xs) (y:ys)
       = case cmp x y of
          LT -> x : loop xs (y:ys)
          EQ ->     loop xs ys
          GT ->     loop (x:xs) ys