2 
test :: [String] -> [String]

test = foldr step []

  where step x ys

          | elem x ys = x : ys

          | otherwise = ys

我正在尝试构建一个包含所有输入的不同字符串的新列表。我的测试数据是：

test ["one", "one", "two", "two", "three"]

预期结果：

["one", "two", "three"]

我是 Haskell 的新手，我确信我错过了一些非常基本和明显的东西，但是已经没有办法去探索了。您能否指出我的想法不足的地方？

实际的反应是[]。似乎永远不会满足第一个保护条件（如果我将其替换为True，则会复制原始列表），因此永远不会构建输出列表。

我的理解是折叠会在列表的每个项目上累积 step 的结果，并将其添加到空列表中。我预计该步骤将测试每个项目是否包含在输出列表中（第一个测试的元素不存在）并将添加任何尚未包含到输出列表中的内容。显然不是 ：-）

4

2 回答 2

7

您的推理是正确的：您只需要切换= x : ys ，= ys以便x在它不是. ys另外，Data.List.nub做这件事。

于 2010-09-08T02:56:05.833 回答
7

想一想：您的代码是说“当 x 在余数中时，将 x 添加到结果中”，即创建一个副本。您只需将其更改为“当 x 不在余数中时，将 x 添加到结果中”即可获得正确的函数。

这个函数有一个重要的不同Data.List.nub：这个函数更严格。因此：

test [1..] = _|_   -- infinite loop (try it)
nub [1..] = [1..]

nub正确地给出了无限列表的答案——这意味着它不需要整个列表来开始计算结果，因此它是流处理游戏中的一个不错的玩家。

它之所以严格是因为它elem是严格的：它在返回结果之前搜索整个列表（假设它没有找到匹配项）。你可以这样写：

nub :: (Eq a) => [a] -> [a]
nub = go []
    where
    go seen [] = []
    go seen (x:xs) | x `elem` seen = go seen xs
                   | otherwise     = x : go (x:seen) xs

注意到目前为止seen的输出如何增长，而您的增长与输出的其余部分一样。前者总是有限的（从开始并一次添加一个），而后者可能是无限的（例如）。所以这个变体可以更懒惰地产生元素。[][1..]

Data.Set如果您使用 a而不是列表，这会更快（O(n log n) 而不是 O(n^2)）seen。但它增加了一个Ord约束。

于 2010-09-08T03:11:48.580 回答