1

我使用的语言是 Haskell 的一个子集，称为 Core Haskell，它不允许使用 Haskell 的内置函数。例如，如果我要创建一个函数来计算项目 x 在列表 xs 中出现的次数，那么我会写：

count = \x -> 
            \xs -> if null xs 
                     then 0
                     else if x == head xs 
                            then 1 + count x(tail xs) 
                            else count x(tail xs)

我正在尝试创建一个函数，该函数输出删除了重复值的列表 xs。例如 remdups (7:7:7:4:5:7:4:4:[]) => (7:4:5:[])

任何人都可以提供任何建议吗？

谢谢！

4

2 回答 2

2

我猜你是学生，而且这是一道作业题，所以我给你部分答案，让你完成。为了编写remdups，拥有一个告诉我们列表是否包含元素的函数会很有用。我们可以使用递归来做到这一点。使用递归时，首先要问自己“基本情况”或最简单的情况是什么。好吧，当列表为空时，显然答案是False（无论字符是什么）。那么现在，如果列表不为空怎么办？我们可以检查列表中的第一个字符是否匹配。如果是，那么我们知道答案是True。否则，我们需要检查列表的其余部分——我们通过再次调用该函数来做到这一点。

elem _ []       = False
elem x (y:ys)   = if x==y
                    then True
                    else elem x ys

下划线 ( _) 仅表示“我不会使用这个变量，所以我什至不会费心给它命名。” 这可以更简洁地写成：

elem _ []       = False
elem x (y:ys)   = x==y || elem x ys

写作remdups有点棘手，但我怀疑你的老师给了你一些提示。处理它的一种方法是想象我们正在处理列表。我们有一部分列表尚未处理，还有一部分列表已处理（并且不包含任何重复项）。假设我们有一个名为 的函数remdupHelper，它接受这两个参数，称为remaining和finished。它将查看 中的第一个字符remaining，并根据该字符是否在中返回不同的结果finished。（该结果可以remdupHelper递归调用）。你会写remdupHelper吗？

remdupHelper = ???

一旦你有了remdupHelper，你就可以开始写了remdups。它只是在初始条件下调用remdupHelper，其中尚未处理任何列表：

remdups l = remdupHelper l []             -- '
于 2013-07-03T17:05:51.443 回答
1

这适用于整数：

removeDuplicates :: [Int] -> [Int]
removeDuplicates = foldr insertIfNotMember []
           where
            insertIfNotMember item list = if (notMember item list)
                          then item : list
                          else list

notMember :: Int -> [Int] -> Bool
notMember item [] = True
notMember item (x:xs)
          | item == x = False 
          | otherwise = notMember item xs

它的工作原理应该是显而易见的。唯一“棘手”的部分是 foldr 的类型是：

(a -> b -> b) -> b -> [a] -> b

但在这种情况下，b 与 [a] 合一，所以它变成：

(a -> [a] -> [a]) -> [a] -> [a] -> [a]

因此，您可以传递函数 insertIfNotMember，其类型为：

Int -> [Int] -> [Int]   -- a unifies with Int
于 2013-07-03T17:37:30.803 回答