Scala - Recursion of an anonymous function

Question

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

Answer 1

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
    }

Answer 2

You actually can define def inside another def. It allows to define function that actually has name which can be referenced and used for recursion. Here is how tails can be implemented:

def tails[T](l: List[T]) = {
    @annotation.tailrec
    def ret(ll: List[List[T]]): List[List[T]] =
        if (ll.last.isEmpty) ll 
        else ret(ll :+ ll.last.tail)

    ret(l :: Nil)
}

This implementation is also tail-recursive. I added @annotation.tailrec annotation in order to ensure that it really is (code will not compile if it's not).

---

You can also use build-in function tails (see ScalaDoc):

List(1,2,3,4).tails.toList

tails returns Iterator, so you need to convert it to list (like I did), if you want it. Also result will contain one extra empty in the end (in my example result would be List(List(1, 2, 3, 4), List(2, 3, 4), List(3, 4), List(4), List())), so you need deal with it.