在 Haskell 中删除或添加列表项

Question

我需要设计一个函数removeOrAdd :: a -> [a] -> [a]。我的直接解决方案：

removeOrAdd :: Eq a => a -> [a] -> [a]
removeOrAdd x xs | x `elem` xs = [x' | x' <- xs, x' /= x]
                 | otherwise   = x : xs

然而，我有一种感觉，我正在做已经被其他人完成的事情。 Haskell 中是否有已经执行此操作的功能？

---

更新：让我们将列表视为一个 Set，我们不希望在列表中有多个 x，否则我们将删除所有这些元素。

- mkUltra

---

我不知道是否有任何函数可以做到这一点，也不确定为什么需要存在这样的函数。向列表中添加元素和删除元素是不同的操作，正如你已经证明的那样，如果确实需要这样做，自己动手也并不难。（请注意，第一个情况的结果可以简化为 filter (/= x) xs） - Robin Zigmond

如果 x 出现多次怎么办？您想删除所有这些项，还是只删除第一个/最后一个？ - Willem Van Onsem

嗯...我不希望有多个 x。所以让我们将其视为集合(Set)。让我更新问题。 - mkUltra

@mkUltra 如果是这样的话，你可能想在每次调用时对列表进行nub。关于列表推导式，有delete :-) - Bergi

@Bergi 我明白你关于 nub 的意思，我想保留列表结构而不是每次都使用 nub，因为它是持久化记录的一部分，所以在受信任的范围内。 - mkUltra

Answer 1

有没有Haskell中已经实现了这个功能的函数？

据我所知，没有，而且在Hoogle上搜索也没有立即列出这样的功能。我认为这很奇怪，因为通常人们的目标是添加或删除，而不是根据条件进行两者。

我们可以通过使其更加懒惰（使其适用于无限列表，其中x从不出现）以及更有效率（我们不会对列表进行两次迭代）来改进上述功能。我们可以使用显式递归来实现：

removeOrAdd :: Eq a => a -> [a] -> [a]
removeOrAdd x = go
    where go [] = [x]
          go (y:ys) | x == y = ys
                    | otherwise = y : go ys

我们在这里对列表进行迭代，直到找到一个等于 x 的元素 y。如果是这种情况，我们返回 ys，并且完成了，因为我们已经删除了该项。如果没有并且我们通过递归到达列表的末尾，我们知道 x 不是列表的一部分，因此我们返回 [x] 来添加该元素。在这里，我们将元素添加到列表的 末尾。

如果列表已排序，则可以将其插入到正确的位置：

removeOrAdd :: <b>Ord</b> a => a -> [a] -> [a]
removeOrAdd x = go
    where go [] = [x]
          go (y:ys) | x == y = ys
                    | y > x = x : y : ys
                    | otherwise = y : go ys

因此，我们在这里保持项目的正确顺序。

- Willem Van Onsem

---

你可能想要强调的区别是，与 OP 的代码相比，你是将元素添加到列表末尾。（当他们将列表视为集合时，这并不重要） - Bergi

谢谢，伙计们！递归优化看起来不错，在我的情况下，物品的位置无关紧要，所以将其添加到列表末尾就可以了。 - mkUltra