I couldn't quite get your code to work as advertised, but I think this snippet should work approximately the same way as yours, under two assumptions: X and Y are sorted, and all elements are unique.
We want to delete from xx
all the elements from yy
. At each step of the way, we just need to compare the first element of each of them (x
and y
, in the function definition). Three things can happen then:
x
is less thany
, which means thatx
is not inyy
, so we can acceptx
x
equalsy
, we rejectx
x
is greater thany
, which means we need to move forward inyy
before we can ascertain whether to reject or acceptx
This is the function definition:
minus :: Ord a => [a] -> [a] -> [a]
minus xx@(x:xs) yy@(y:ys) = case (compare x y) of
LT -> x : minus xs yy
EQ -> minus xs ys
GT -> minus xx ys
minus xs _ = xs