1

我有一个作业问题，要求我使用 lambda 编写一个函数，该函数使用一个数字列表并删除除每个数字第一次出现之外的所有数字。我的功能是我认为很好，除了它产生错误的结果！它生成一个列表，其中包含每个数字的最后一次出现。它生成一个与正确列表具有相同值的列表，只是顺序不同。这是我的代码：

    (define (remove-duplicates numlist)
      (foldr (lambda (a b) 
               (cond
                 [(not (member? a b)) (cons a b)]
                 [else b])) empty numlist))

我尝试过使用foldl而不是，foldr但毫不奇怪，它会产生正确的列表，但相反。有没有一种方法可以生成正确的列表，而无需foldl使用另一个 lambda 表达式来反转由创建的列表？

请记住，这是作业，所以请不要明确回答。

感谢大家！

4

1 回答 1

1

从语义上考虑 foldr 的行为方式。它从列表的最右侧元素开始，并执行折叠，向左移动。这意味着在您的 lambda 函数中，a直接表示迄今为止折叠列表左侧的元素，并b表示将所有内容折叠到列表元素右侧的结果a。考虑到这一点，请考虑：

[(not (member? a b)) (cons a b)]
[else b]

您检查列表是否b已包含a. 如果确实如此，那么您丢弃a，保持b原样。这解释了为什么您的代码保留最后（最右边）出现，而不是第一次出现。如果你想正确弃牌，那么你必须改变你的逻辑。您需要以某种方式“清除”它包含b的违规元素。a

[(not (member? a b)) (cons a b)]
[else (cons a (purge a b))]

这样，您最终将只保留每个唯一元素的最左边而不是最右边的出现。member?同时执行可能是明智的purge，因为它们都必须遍历列表；这将需要额外的重构。

请注意，由于该函数无论如何都需要O(n 2 )时间，因此向版本添加O(n)反向确实不会影响时间复杂度foldl。

于 2011-11-19T22:03:35.640 回答