Questions and Completion

To receive credit for completing the worksheet, you must complete the corresponding quiz (it is just a checkbox) on D2L when you have finished the worksheet.

If you have questions as you go through this worksheet, please feel free to post them on the discussion forum.

Tail Recursion

Scala - Looping in Scala with a Function

Write Scala code that uses a tail-recursive function to print the following:

1 potato
2 potato
3 potato
4 potato

You should define a function for this.

Include a tailrec annotation so that the Scala system tells you if your function is not tail recursive.

Solution: Scala - Looping in Scala with a Function

Scala - Counting Values

Here is Java code to count the number of integers in a linked list that are between low and high values.

public class CountingValues {
  static class Node {
    int item;
    Node next;

    public Node (int item, Node next) { 
      this.item = item; 
      this.next = next; 
    }
  }

  static int count (Node data, int low, int high) {
    int result = 0;
    while (data != null) {
      if (low <= data.item && data.item <= high) {
        result = result + 1;
      }
      data = data.next;
    }
    return result;
  }

  public static void main (String[] args) {
    Node data = null;
    for (int i = args.length - 1; i >= 0; i--) {
      data = new Node (Integer.parseInt (args[i]), data);
    }

    System.out.printf ("count (..., 5, 10) = %d%n", count (data, 5, 10));
  }
}

$ javac CountingValues.java 
$ java CountingValues 1 2 3 4 5 6 7 8 9 10 11 12
count (..., 5, 10) = 6

Your task is to rewrite the count function in Scala. Your definition should be a tail-recursive function.

Solution: Scala - Counting Values

Scala - Which Functions Are Tail Recursive?

Consider each of the following Scala functions. For each Scala function, is it tail recursive? Test your answers by adding a tailrec annotation and pasting the function definition into the Scala console.

/* The Scala library includes many other functions on lists that are common.
 * Below we define our own versions of these functions for pedagogical purposes,
 * but normally the library versions would be used instead.
 */

def append [X] (xs:List[X], ys:List[X]) : List[X] =
  xs match
    case Nil   => ys
    case z::zs => z :: append (zs, ys)

def flatten [X] (xss:List[List[X]]) : List[X] =
  xss match
    case Nil     => Nil
    case ys::yss => ys ::: flatten (yss)

/* The "take" function takes the first n elements of a list. */
def take [X] (n:Int, xs:List[X]) : List[X] =
  if n <= 0 then
    Nil
  else
    xs match
      case Nil   => Nil
      case y::ys => y :: take (n - 1, ys)

/* The "drop" function drop the first n elements of a list. */
def drop [X] (n:Int, xs:List[X]) : List[X] =
  if n <= 0 then
    xs
  else 
    xs match
      case Nil   => Nil
      case y::ys => drop (n - 1, ys)

val sampleList : List[Int] = (1 to 12).toList
val takeresult : List[Int] = take (3, sampleList)
val dropresult : List[Int] = drop (3, sampleList)

/* Reverse a list.  This version is straightforward, but inefficient.  Revisited later on. */
def reverse [X] (xs:List[X]) : List[X] =
  xs match
    case Nil   => Nil
    case y::ys => reverse (ys) ::: List (y)

/* zip takes two lists and creates a single list containing pairs from the two lists
 * that occur at the same position.  The definition shows more sophisticated pattern
 * matching: the use of wildcards; overlapping patterns; and decomposing pairs and
 * lists simultaneously.  Note that the "xs" and "ys" in the third case shadow the
 * "xs" and "ys" parameters to the function.
 */
def zip [X,Y] (xs:List[X], ys:List[Y]) : List[(X,Y)] = (xs, ys) match
  case (Nil, _)       => Nil
  case (_, Nil)       => Nil
  case (x::xs, y::ys) => (x, y) :: zip (xs, ys)

val ziplist = zip (List (1, 2, 3), List ("the", "rain", "in", "spain"))

/* unzip decomposes a list of pairs into a pair of lists.
 * The recursive case illustrates pattern-matching the result of the
 * recursive call in order to apply an operation to the elements.
 */
def unzip [X,Y] (ps:List[(X,Y)]) : (List[X], List[Y]) =
  ps match
    case Nil        => (Nil, Nil)
    case (x, y)::qs => 
      val (xs, ys) = unzip (qs)
      (x :: xs, y :: ys)

val unziplist = unzip (ziplist)

def reverse2 [X] (xs:List[X]) : List[X] =
  def aux (xs:List[X], result:List[X]) : List[X] = xs match
    case Nil   => result
    case y::ys => aux (ys, y :: result)

  aux (xs, Nil)

Solutions

Solution: Scala - Looping in Scala with a Function

import scala.annotation.tailrec

@tailrec
def foo (n:Int) : Unit =
  if n <= 4 then 
    println ("%d potato".format (n))
    foo (n + 1)

scala> foo (1)
1 potato
2 potato
3 potato
4 potato

Solution: Scala - Counting Values

Here is one way to structure the program. The tail-recursive aux function is nested inside count, which means it can only be called from inside count.

def count (xs:List[Int], low:Int, high:Int) : Int =
  def aux (ys:List[Int], result:Int) : Int =
    ys match
      case Nil                            => result
      case z::zs if low <= z && z <= high => aux (zs, result + 1)
      case _::zs                          => aux (zs, result)
  aux (xs, 0)

scala> count (List (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12), 5, 10)
res1: Int = 6