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

The title of your question included "anonymous". Those are not anonymous functions, which would have the form `(inputs) => expression`, i.e. no name. I don't know if in Scala, it possible to recurse a function with no name. In Javascript, it can be done with the deprecated [`callee`](https://developer.mozilla.org/en/JavaScript/Reference/Functions_and_function_scope/arguments/callee). — Shelby Moore III, Dec 04 '11 at 20:23

Tomasz Nurkiewicz · Accepted Answer · 2011-12-01T20:46:00.837

4

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
    }

edited Dec 01 '11 at 20:46

answered Dec 01 '11 at 20:12

Tomasz Nurkiewicz

334,321
69
703
674

Great that works but I'm only understanding about half of whats going on. The main thing I'm not understanding is where the `x` is coming from. And thanks about the length info; – locrizak Dec 01 '11 at 20:19
@locrizak: well, I don't understand where `x` is coming from either, there is no `x` in my solution ;-). Try to go through this code with a paper and pencil, you'll see how recursion works here. – Tomasz Nurkiewicz Dec 01 '11 at 20:27
WTF! I guess I'm seeing things! Where does the `h` come from in `case h`? – locrizak Dec 01 '11 at 20:32
The h is a variable whose value comes from the object being matched. It just means :: tail. If you wanted to, it could then be used in the case statement. For example, you could say: case first :: second :: third :: Nil => println(first + " " + second + " " + third). This will match any list with exactly three elements and assign those elements to the variables first, second, and third. Usage: scala> List(1,2,3) match { case first :: second :: third :: Nil => println(first + " " + second + " " + third) case _ => println("No match") } 1 2 3 List(1,2,3,4) prints "No match" – Austen Holmes Dec 01 '11 at 20:41
It is part of the *pattern matching*. A very broad topic, see [The Point of Pattern Matching in Scala](http://www.artima.com/scalazine/articles/pattern_matching.html). You'll find the same constructs in multiple languages from Prolog, through Haskell to Clojure. – Tomasz Nurkiewicz Dec 01 '11 at 20:42
This solution looks nice, but unfortunately it's not tail-recursive. (and I believe that @locrizak tries to implement tail-recursive version) – tenshi Dec 01 '11 at 20:42
Thanks a lot guys @tenshi I'm just trying to accomplish the same task in as many ways as I can so I can get a good handle on the language. @tomasz Pattern matching is in the `intermediate` labs, I'm only on the `Basic` Ones and trying to take it one step at a time :) – locrizak Dec 01 '11 at 20:49

tenshi · Answer 2 · 2011-12-01T20:47:50.373

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.

@locrizak: I don't think that you can have recursion with first-class function, you need `def` for this. — tenshi, Dec 01 '11 at 20:32

score 1 · Answer 3 · edited May 23 '17 at 11:51

What you are doing wrong is this:

val ret : List[List[T]]

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

ret(ll :+ ll.last.init)

That mean you are calling the method apply on a list of list of T. The apply method for lists take an Int parameter, and returns an element with that index. For example:

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

I assume you wanted to write val ret: List[List[T]] => List[List[T]], that is, a function that takes a List[List[T]] and returns a List[List[T]]. You'd have other problems then, because val is referring to itself in its definition. To get around that, you could replace it with a 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, the easy solution is to put one def inside the other, like tenshi suggested.

score 1 · Answer 4 · answered Dec 01 '11 at 20:55

1

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 start value/accumulator. The second function is the modifier. Typically, it modifies the start value, which is then passed to every element in the list. I included a println so you can see the accumulator as the list is iterated over.

answered Dec 01 '11 at 20:55

Austen Holmes

1,889
14
9

Ballin! Do you know if there is any extra overhead when using foldLeft over the other examples? – locrizak Dec 01 '11 at 21:02
I don't think so. Take a look at the source: https://lampsvn.epfl.ch/trac/scala/browser/scala/tags/R_2_9_1_final/src//library/scala/collection/LinearSeqOptimized.scala#L1 106 override /*TraversableLike*/ 107 def foldLeft[B](z: B)(f: (B, A) => B): B = { 108 var acc = z 109 var these = this 110 while (!these.isEmpty) { 111 acc = f(acc, these.head) 112 these = these.tail 113 } 114 acc 115 } – Austen Holmes Dec 01 '11 at 21:16
Wow that didn't post cleanly. Anyway, there is shorthand for fold left /: I always forget it and just type foldLeft – Austen Holmes Dec 01 '11 at 21:17
A lot of the scala collections libraries were written to look like they are recursive, when really they are written in an iterative way due to the constraints of the jvm and stack size. This would be an example. There is a good explanation of what they attempted to achieve here: http://www.artima.com/scalazine/articles/scala_collections_architecture.html (also taken from the book Programming in Scala, which I highly recommend.) – Austen Holmes Dec 01 '11 at 21:20
Yup I've got that and about 250 pages in. I wanted to try out some exercises my self so I found scala labs. Now I'm bouncing back and forth every time there's a exercise I don't understand – locrizak Dec 01 '11 at 21:23

Scala - Recursion of an anonymous function

4 Answers4