这是Python代码的Haskell等效代码

Question

我在学习Python之后开始学习Haskell，我认为编写一个函数来查找一个序列中所有不在另一个序列中的项目（其中两个序列都具有可比较的元素）将是一个有趣的练习。我很容易地用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循环。我猜想我可以使用无限递归，但由于有两个循环，我不知道是否需要两个函数或其他什么。

- rlms

---

filter (not . (\elem` domain)) seq的意思是：从seq序列中过滤掉所有不属于domain元素的内容。更简单地说，就是将seq序列中不在domain` 中的元素过滤掉。 - Yuras

我不能确定你的Python代码是否做了你想做的事情。它不仅仅是两个列表的差异。顺便说一句，在Haskell中，你可以使用Data.List.(\\)计算它们的差异。 - daniel gratzer

http://hackage.haskell.org/package/data-ordlist-0.4.6/docs/src/Data-List-Ordered.html#minus - Daniel Wagner

您可以使用“pipes”获得类似于协程的行为。您可以使用“Foldable.toList”获得类似于“iter”的行为。 - J. Abrahamson

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  

- pdpi

---

Python 中的生成器 (Generators) 翻译成 Haskell 就是 "guarded" 或者 "productive" 递归。这时我们会有像 SomeConstructor foo bar (recursion goes here) 这样的东西。如果这个递归陷入无限循环, 我们仍然可以对 SomeConstructor 进行模式匹配，只要我们不强制评估它的第三个字段。在上面的例子中，这可以通过 x : ... 来实现。如果您因某种原因对此背后的理论感到有趣，那么共归纳、协调数据和互递归是相关概念。 - daniel gratzer

我认为你的意思是 LT -> x : minus xs yy。 - rampion

GT这个情况看起来很奇怪：在Python代码中，当d > s时，我们会产生d并跳出循环，所以我们同时前进到xs和ys，是吗？也许GT -> x: minus xs ys执行相同的操作？ - chi

@chi: 我认为这是 Python 中的一个错误，因为它使得 inverse([1,2,3,4],[2,3,4]) 返回了 2、3、4。 - rampion

@rampion 哦，我明白了。我只看了Python程序做了什么，而没有看它的目的。 :) - chi