哈斯克尔守卫没有得到满足

Question

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,原始列表被复制),因此输出列表永远不会被构建.

我的理解是,折叠会累积列表中每个项目的步骤结果,将其添加到空列表中.我预计该步骤将测试每个项目是否包含在输出列表中(测试的第一个元素不在那里)并将添加尚未包含在输出列表中的任何内容.显然不是 :-)

Answer 1

你的推理是正确的:你只需要切换= x : ys ,= ys这样你就可以添加x它不是元素的时候ys.此外,Data.List.nub这是确切的事情.

Answer 2

想一想:你的代码是说"当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而不是列表,这将更快(O(n log n)而不是O(n ^ 2))seen.但它增加了一个Ord约束.