Scala - Recursion of an anonymous function

I'm working through the scala labs stuff and I'm building out a function that will, in the end, return something like this: tails(List(1,2,3,4)) = List(List(1,2,3,4), List(2,3,4), List(3,4), List(4), List())

I got this working by using two functions and using some recursion on the second one.

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

This is all good a great but it's bugging me that I need two functions to do this. I tried switching: trailUtil(List() ::: List(l)) for an anonymous function but I got this error type mismatch; found :List[List[T]] required:Int from the IDE.

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

Could someone please point me to what I am doing wrong, or a better way of doing this that would be great.

(I did look at this SO post but the different type are just not working for me):

Answers


What about this:

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

And a little bit less idiomatic version:

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

BTW try to avoid List.length, it runs in O(n) time.

UPDATE: as suggested by tenshi, tail-recursive solution:

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

Need Your Help

Why is this many-to-many relation changing whitout me asking for it, using the Django ORM?

django orm many-to-many

I have a recursive M2M relationship with an indicator class. An indicator is a int, or a calculated value from 2 indicators:

White Screen using mysqli

php table mysqli registration

I attempted PHP and MySQL for the first time today following a tutorial, I was told using $MySQL was outdated and told to use $mysqli which I've attempted. I've uploaded my page to my server on ip...

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.