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.

Overtrade

filter (not . (`elem` domain)) seq. Or in plain english: filter out everything that is not element of domain – Glance

I'm not so sure your python code does what you think it does.. It's not just the difference of two lists. Which by the way, you can calculate in Haskell with Data.List.(\\) – Opus

hackage.haskell.org/package/data-ordlist-0.4.6/docs/src/… – Linkwork

You can get coroutine-like behavior using pipes. You can get iter like behavior using Foldable.toList. – Staford

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  

Attitudinize

Generators in Python translate to "guarded" or "productive" recursion in Haskell. That's where we have something like SomeConstructor foo bar (recursion goes here). If if that recursion loops forever, we can still pattern match on SomeConstructor so long as we don't force the evaluation of it's third field. In the example above, this is done with x : .... If the theory behind this is interesting to you for whatever reason, coinduction, codata, and corecursion are the relevant concepts. – Opus

I think you mean LT -> x : minus xs yy. – Supply

The GT case looks strange: in the Python code when d > s we yield d and break, so we advance to both xs and ys, I think? Maybe GT -> x : minus xs ys performs the same? – Examinee

@chi: I'd argue that's a bug in the python since it makes inverse([1,2,3,4],[2,3,4]) yield 2, 3, 4 – Supply

@Supply Ah, I see. I did not look at what the Python program was meant to do, only at what it did. :) – Examinee