Scala – 匿名函数的递归

发布时间：2020-12-16 18:52:41 所属栏目：安全来源：网络整理

导读：我正在研究 scala labs的东西,我正在构建一个函数,最终会返回这样的东西：尾(列表(1,2,3,4))=列表(列表(1,4),列表(2,列表(3,列表(4),列表( )) 我通过使用两个函数并在第二个函数上使用一些递归来实现此功能. def tails[T](l: List[T]): List[List[T]] = { i

我正在研究 scala labs的东西,我正在构建一个函数,最终会返回这样的东西：
尾(列表(1,2,3,4))=列表(列表(1,4),列表(2,列表(3,列表(4),列表( ))

我通过使用两个函数并在第二个函数上使用一些递归来实现此功能.

def tails[T](l: List[T]): List[List[T]] = {
    if ( l.length > 1 )trailUtil(List() ::: List(l))
    else List() ::: List(l);
}

def trailUtil[T](l:List[List[T]]) : List[List[T]] = {
    if ( l.last.length == 0)l
    else trailUtil(l :+ l.last.init);
}

这一切都很好,但是我需要两个函数才能做到这一点.我尝试切换：trailUtil(List()::: List(l))为匿名函数,但我得到此错误类型不匹配; found：需要列表[List [T]]：来自IDE的Int.

val ret : List[List[T]] = (ll:List[List[T]]) => {
    if ( ll.last.length == 0) ll else ret(ll :+ ll.last.init)
}
ret(List() ::: List(1))

有人可以指出我做错了什么,或者更好的做法,这将是伟大的.

(我确实看过this SO帖子,但不同的类型对我不起作用)：

解决方法

那这个呢：

def tails[T](l: List[T]): List[List[T]] = 
  l match {
    case h :: tail => l :: tails(tail)
    case Nil => List(Nil)
  }

还有一点不那么惯用的版本：

def tails[T](input: List[T]): List[List[T]] =
    if(input.isEmpty)
        List(List())
    else
        input :: tails(input.tail)

BTW尝试避免List.length,它在O(n)时间内运行.

更新：正如tenshi所建议的那样,尾递归解决方案：

@tailrec def tails[T](l: List[T],init: List[List[T]] = Nil): List[List[T]] =
    l match {
        case h :: tail => tails(tail,l :: init)
        case Nil => init
    }

（编辑：李大同）

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