Questions and Completion

There is nothing to hand in for the worksheet, but you should definitely work through it in order to prepare for the quiz and homework.

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

Tail Recursion

Scheme - Looping in Scheme

Write a Scheme expression that uses a let special form with a loop variable to print the following:

1 potato
2 potato
3 potato
4 potato

You should not define a function for this.

Solution: Scheme - Looping in Scheme

Scheme - Looping in Scheme with a Function

Write Scheme 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.

Solution: Scheme - Looping in Scheme with a Function

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

Scheme - 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 Scheme. Your definition should be a tail-recursive function.

Solution: Scheme - Counting Values

Scala - Counting Values

Repeat the previous “Counting Values” task 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: Scheme - Looping in Scheme

(let loop ([n 1])
  (if (> n 4)
      ()
      (begin
        (display (string-append (number->string n) " potato\n"))
        (loop (+ n 1)))))

Solution: Scheme - Looping in Scheme with a Function

(define (foo n)
  (if (> n 4)
      ()
      (begin
        (display (string-append (number->string n) " potato\n"))
        (foo (+ n 1)))))

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: Scheme - Counting Values

(define (count-aux xs low high result) 
  (if (equal? xs ())
      result
      (if (and (<= low (car xs)) (<= (car xs) high))
          (count-aux (cdr xs) low high (+ 1 result))
          (count-aux (cdr xs) low high result))))

(define (count xs low high) 
  (count-aux xs low high 0))


; Alternative version

(define (count-alternate xs low high) 
  (let loop ([xs xs] [result 0])
    (if (equal? xs ())
        result
        (if (and (<= low (car xs)) (<= (car xs) high))
          (loop (cdr xs) (+ 1 result))
          (loop (cdr xs) result)))))

#;> (count-aux '(1 2 3 4 5 6 7 8 9 10 11 12) 5 10 0)
6

#;> (count '(1 2 3 4 5 6 7 8 9 10 11 12) 5 10)
6

#;> (count-alternate '(1 2 3 4 5 6 7 8 9 10 11 12) 5 10)
6

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