我必须使用递归编写一个Union函数
输出必须是两个列表的并集(无重复(。我的老师说实现必须是递归的，我们不能两次浏览列表，但我不认为我能想出一种不浏览两次列表就解决问题的方法吗？
我的想法可以解决问题(但需要浏览两次列表(：-合并然后删除重复项-对列表进行排序，然后合并
任何提示或帮助都将不胜感激
编辑：好吧，所以我必须通过这样做来合并这两个列表：
union1 :: (Eq a) => [a] -> [a] -> [a]
union1 xs [] = xs
union1 [] ys = ys
union1 (x:xs)(y:ys) = x:y:union1(xs)(ys)
然后我想我可以使用nub或类似的功能来删除重复项，但我一直在想，因为那样我会浏览两次列表，对吧？
什么是列表并集
我想首先指出，你的老师给你的要求有点含糊。此外，多集上的并集(也就是可以有重复的集，比如列表(在数学中有两个不同的定义(其他来源(。我不是数学家，但以下是我从各种互联网上收集到的信息。这里有一个定义：
λ> [1,2,2,3,3,3] `unionA` [1,2,2,2,3] --also called multiset sum
[1,1,2,2,2,2,2,3,3,3,3]
如果您不担心订购，这只是(++)。这是另一个：
λ> [1,2,2,3,3,3] `unionB` [1,2,2,2,3]
[1,2,2,2,3,3,3] --picks out the max number of occurrences from each list
更令人困惑的是，Data.List实现了一个有点古怪的第三种类型的并集，它将左输入与右输入区别对待。以下是在Data的union源代码注释中找到的大致文档。列表：
union函数返回两个列表的列表并集。重复项和第一个列表的元素会从第二个列表中删除，但如果第一个列表包含重复项，则结果也会删除。例如，
λ> "dog" `union` "cow" "dogcw"
这里，"；列表的并集"；可供选择。所以，除非你有示例输入和输出，否则我不知道你的老师想要哪一个，但由于目标可能是让你学习递归，请继续阅读…
删除重复项
在Haskell中，从无序列表中删除重复项可以在线性时间内完成，但解决方案涉及随机访问数据结构，如Arrays，或称为"的东西；生产稳定无序鉴别器"；，如在CCD_ 4封装中。我不认为这是你的老师想要的，因为第一个在命令式编程中也很常见，而第二个对于初学者Haskell课程来说太复杂了。你的老师可能的意思是，你应该只明确地遍历每个列表一次。
现在是实际的代码。在这里，我将向您展示如何实现union#3，从您编写的内容开始，并且仍然只(显式(遍历列表一次。您已经有了基本的递归方案，但不需要在两个列表上都递归，因为我们选择了选项#3，因此返回的第一个列表保持不变。
实际代码
您将在下面的代码中看到，第一个列表用作"；"累加器"：在第二个列表上递归时，我们检查第一个列表中的每个元素是否有重复，如果没有重复，我们将其附加到第一个列表。
union [] r = r
union l [] = l
unionR ls (r:rs)
| r `elem` ls = unionR ls rs --discard head of second list if already seen
--`elem` traverses its second argument,
--but see discussion above.
| otherwise = unionR (r:ls) rs --append head of second list
附带说明一下，您可以使用fold:使其可读性更强
union xs = foldl step xs where --xs is our first list; no recursion on it,
--we use it right away as the accumulator.
step els x
| x `elem` els = els
| otherwise = x : els