这个Python代码的Haskell等价实现

Question

我在学习Haskell，之前学的是Python。我觉得写一个函数，找出一个序列中不在另一个序列里的所有元素（这两个序列里的元素可以比较）会是个有趣的练习。我在Python中很轻松地写了这个代码：

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

（这里的seq和domain都是排好序的）

不过，我在把这个代码转换成Haskell时遇到了困难。我想我可以用列表（可能是无限的）来代替ss和dd，我猜s = next(ss)可以理解为s = head ss，而ss = tail ss也是类似的，但我不知道怎么把这些转换成Haskell。我也搞不清楚该怎么处理那两个while循环。我想我可以用无限递归，但因为有两个循环，我不确定是不是需要两个函数，或者该怎么做。

Answer 1

我没能让你的代码如你所说的那样工作，但我觉得这个代码片段在两个假设下应该能大致实现和你的代码相同的功能：X和Y是排好序的，并且所有元素都是唯一的。

我们的目标是从xx中删除所有yy里的元素。在每一步中，我们只需要比较它们的第一个元素（在函数定义中是x和y）。接下来可能会发生三种情况：

• x小于y，这意味着x不在yy中，所以我们可以保留x
• x等于y，我们就拒绝x
• x大于y，这意味着我们需要在yy中向前移动，才能确定是拒绝还是接受x

这是函数的定义：

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