如何通过模式匹配从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在它的结果前面添加.在随后的部分破坏尾递归的想法,因为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) 
  }

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

2. 您需要另一个递归函数 - contains用于指示给定元素是否包含在列表中.一旦你有了这个,只需用case上面的代码替换上面的第二个 子句

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

你的工作已经完成!

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