如何通过模式匹配从Scala中的列表中删除重复项？

发布时间：2020-12-16 10:05:53 所属栏目：安全来源：网络整理

导读：作为家庭作业,我必须编写一个函数,从列表中删除重复项.它应该是递归的并且具有模式匹配.我不允许使用head,tail,contains等列表函数. 对于排序列表,我提出了这个解决方案： def remove(u:List[Int]):List[Int] = { u match { case Nil = u case hd::hd2::tl =

作为家庭作业,我必须编写一个函数,从列表中删除重复项.它应该是递归的并且具有模式匹配.我不允许使用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)
  }
}

如何处理未排序的列表？

解决方法

我不会为你做功课,但希望,这会有所帮助.

>你想让你的函数尾递归.这意味着递归调用出现在函数的最后一个位置,这样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) 
  }

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

>你需要另一个递归函数 – contains – 它告诉一个给定元素是否包含在列表中.一旦你有了这个,只需用上面的东西替换上面的第二个case子句

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

你的工作已经完成！

>如果要保留列表元素的原始顺序,则需要在之后将其反转(替换大小写Nil =>结果,大小写为Nil => result.reverse)…如果不允许使用.反过来,这对你来说是另一个很好的锻炼.你如何递归地反转列表(尾部)？

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!