Scala - Anonymous Function Recursion

Question

I am working on scala labs material and I am creating a function that will eventually 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 using two functions and using some recursion on the second.

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

All this is good, but it pushes me to the fact that for this I need two functions. I tried switching: trailUtil(List() ::: List(l)) for an anonymous function, but I got this error type mismatch; found :List[List[T]] required:Int 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)) 

Can someone tell me what I'm doing wrong, or is the best way to do this, which would be great.

(I watched this one , but different types just don't work for me):

Answer 1

How 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 slightly less idiomatic version:

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

Try to avoid List.length , it works in O (n) time.

UPDATE: as suggested by tenshi, a 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

In fact, you can define def inside another def . It allows you to define a function that actually has a name that can be referenced and used for recursion. Here's 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 the annotation @annotation.tailrec to make sure it is valid (the code will not compile if it is not).

---

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

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

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

Answer 3

What you are doing wrong is the following:

 val ret : List[List[T]] 

So ret is a list of T. Then you do this:

 ret(ll :+ ll.last.init) 

This means that you call the apply method in the list of T. The apply method for lists takes an Int parameter and returns an element with this index. For instance:

 scala> List("first", "second", "third")(2) res0: java.lang.String = third 

I suppose you wanted to write val ret: List[List[T]] => List[List[T]] , that is, a function that takes List[List[T]] and returns a List[List[T]] . Then you will have other problems because val refers to itself in its definition. To get around this, you can replace it with lazy val :

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

But, of course, a simple solution is to put one def inside another, for example tenshi .

Answer 4

You can also use folding:

 val l = List(1,2,3,4) l.foldLeft(List[List[Int]](l))( (outerList,element) => { println(outerList) outerList.head.tail :: outerList }) 

The first parameter list is your initial value / battery. The second function is a modifier. Typically, it changes the initial value, which is then passed to each item in the list. I turned on println so you can see the battery when the list repeats.