scala - 如何使用模式匹配从 Scala 列表中删除重复项？

Question

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

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)
  }
}

我如何为未排序的列表做这件事？

Answer 1

我不会为你做作业，但希望这会有所帮助。

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

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

  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) 
  }

(注意，这里的两个递归调用都在尾部位置——调用返回后没有什么可做的，因此可以在调用递归之前从堆栈中清除之前的条目)。

1. 您需要另一个递归函数 - contains - 告诉给定元素是否包含在列表中。一旦你有了它，只需用类似

   的东西替换上面的第二个 case 子句

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

你的工作完成了!

1. 如果你想保留列表元素的原始顺序，你需要在之后反转它(将case Nil => result替换为case Nil => result.reverse) ... 如果您也不允许在这里使用 .reverse，那对您来说将是另一个不错的练习。如何递归地反转列表(尾部)？