Is there a lazy way to write a minus function (remove items from the 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 as follows:

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

with output: [99,44,23423]

I wrote this because I look at the Project Euler 7 issue, and the Eratosthenes sieve seems to be the right tool, and that was, but I continued to read the Wikipedia page and got to the bottom of the Euler sieve.

I tried to copy / paste the code and run it in GHCi, but my version of GHCi does not have a module called Data.OrdList, and I could not 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 replace my minus function there, I get an error from memory because my function is not lazy.

Is there a way to make a lazy minus function?

Does my minus function use the same thing as the minus function in the Wikipedia article?

Answer 1

As stated in sepp2k, the minus implementation should accept ordered lists. Here's 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 2

Is there a way to make a lazy minus function?

If you do not assume that the input lists are ordered (and you are not allowed to sort them), they are not. You need to know if the first element of list1 is in list2 before you know what the first element of the result will be. Thus, you cannot get around to evaluating the entire second list before creating one element in the worst case.

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

And since your input list is actually ordered, such a minus function will work just fine for your needs.

Answer 3

Google has surpassed Google.

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 xy of LT -> x : loop xs (y:ys) EQ -> loop xs ys GT -> loop (x:xs) ys