Haskell equivalent of this Python code

Question

I'm learning Haskell after Python, and I thought that making a function that finds all the items in a sequence that aren't in another (where both sequences have elements that can be compared) would be an interesting exercise. I wrote some code for this in Python easily:

def inverse(seq, domain):
    ss = iter(seq)
    dd = iter(domain)
    while True:
        s = next(ss)
        while True:
            d = next(dd)
            if d != s:
                yield d
            if d >= s:
                break

(where both seq and domain are sorted)

However, I struggled to turn this code into Haskell. I presume I'd just use lists (that could be infinite) instead of ss and dd, and I guess I'd use s = next(ss) is the same as s = head ss and ss = tail ss, but I can't figure out how I'd translate that into Haskell. I also can't work out what I'd do with the two while loops. I presume I could use infinite recursion, but as there are two loops I don't know if that would need two functions or what.

Answer 1

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 than y, which means that x is not in yy, so we can accept x
• x equals y, we reject x
• x is greater than y, which means we need to move forward in yy before we can ascertain whether to reject or accept x

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