如何通过模式匹配从Scala中的列表中删除重复项? [英] How can I remove duplicates from a list in Scala with pattern matching?

问题描述

作为家庭作业，我必须编写一个函数，该函数将从列表中删除重复项.它应该是递归的并且具有模式匹配.我不允许使用列表函数，例如head，tail，contains等. 对于排序列表，我想出了以下解决方案:

As homework i have to write a function that will remove duplicates from a list. It should be recursive and with pattern matching. I am not allowed to use list functions like head,tail,contains,etc... .
For sorted lists i came up with this solution:

def remove(u:List[Int]):List[Int] = {
  u match { case Nil => u
  case hd::hd2::tl => if(hd == hd2) remove(hd2::tl) else hd :: remove(hd2::tl)
  case hd::tl => hd :: remove(tl)
  }
}

如何处理未排序的列表?

How can i do it for unsorted lists?

推荐答案

我不会为您做家庭作业，但希望会有所帮助.

I won't do your homework for you, but hope, this will help.

1. 您要使函数 tail-recursive .这意味着递归调用出现在函数的最后一个位置，以便jvm可以在调用之前从堆栈中清除之前的调用(这使它执行起来非常像循环，而无需在堆栈上增加额外的空间) .在您的原始解决方案中，是这样的语句，使其不尾递归:hd :: remove(tl):您必须调用递归调用，然后 then 在其结果前加上hd. then 部分打破了尾递归的概念，因为jvm必须记住在堆栈上递归调用完成后要返回的位置.

1. You want to make your function tail-recursive. That means that the recursive call appears in the very last position of the function, so that the jvm can clear up the previous call from the stack before invoking it (it makes it execute very much like a loop, without requiring additional space on stack). In your original solution it is statements like this, that make it not tail-recursive: hd :: remove(tl): you have to invoke the recursive call, and then prepend hd to its result. The then part breaks the idea of tail recursion, because jvm has to remember on stack the place to return to after the recursive call is finished.

通常可以通过将递归函数的最终结果作为参数来避免这种情况:

This is typically avoided by carrying the final result of the function through the recursion as an argument:

  def remove(u: List[Int], result: List[Int] = Nil): List[Int] = u match {
     case Nil => result
     case a :: b :: tail if a == b => remove(b :: tail, result)
     case head :: tail => remove(tail, head :: result) 
  }

(请注意，这里的两个递归调用都位于尾部位置-调用返回后无需执行任何操作，因此可以在调用递归之前从堆栈中清除前一个条目).

(Note, that both recursive invocations here are in the tail position - there is nothing left to do after the call returns, so the previous entry can be cleared from the stack prior to invoking the recursion).

1. 您需要另一个递归函数-contains-告诉列表中是否包含给定元素.一旦有了，只需将上面的第二个case子句替换为

1. You need another recursive function - contains - that tells whether a given element is contained in a list. Once you have that, just replace the second case clause above with something like

case head :: tail if contains(head, result) => remove(tail, result)

您的工作完成了！

1. 如果要保留列表元素的原始顺序，则以后需要reverse(将case Nil => result替换为case Nil => result.reverse)...如果不允许在此处使用.reverse同样，这对您来说也是另一种不错的练习.您如何递归地反转列表(尾部)?

1. If you want to preserve the original order of elements of the list, you will need to reverse it afterwards (replace case Nil => result with case Nil => result.reverse) ... If you are not allowed to use .reverse here too, that's going to be another nice exercise for you. How do you reverse a list (tail-)recursively?

这篇关于如何通过模式匹配从Scala中的列表中删除重复项?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！