Worksheet Functional Programming

1. Questions and Completion
2. Java
- 2.1. Java Parametric Polymorphism Linked Lists
3. Scala - Functional Programming
4. Tail Recursion
5. Lists
- 5.1. flatMap for Lists
6. Solutions

1. Questions and Completion

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

2. Java

2.1. Java Parametric Polymorphism Linked Lists

Write a Java linked list class that uses parametric polymorphism. There should be a Node class with a type parameter, i.e., Node<X>.

Add code to calculate the length of such a list and to test your length function. Try compiling and running it.

Solution: Java Parametric Polymorphism Linked Lists

3. Scala - Functional Programming

3.1. Builtin Control Structures - While Loops

Use a while loop in Scala to print each element of a linked list. Use a var with a copy of the argument because parameter bindings are val. You do not need to use pattern-matching for this function, but you would normally use pattern-matching in Scala.

def printList [X] (xs:List[X]) : Unit = {
  var tmp = xs
  ...
}

Solution: Scala - Builtin Control Structures - While Loops

3.2. Common Higher-Order Functions

Write Scala functions that take a list of integers xs:List[Int] as a parameter and:

print each integer in xs (use the method foreach from the List class)
create a new list with the squares of each integer from xs (use the method map from the List class)
create a new list containing the odd numbers from xs (use the method filter from the List class)
return an Option[Int] with the first integer greater than or equal to 5 if it exists in xs (use the method find from the List class; look in the Scala API documentation!)
count the number of integers greater than or equal to 5 in xs (use the method count from the List class; look in the Scala API documentation!)
return a Boolean indicating whether there are any integers greater than or equal to 5 in xs (use the method exists from the List class; look in the Scala API documentation!)
return a Boolean indicating whether all integers in xs are greater than or equal to 5 (use the method forall from the List class; look in the Scala API documentation!)

Solution: Scala - Common Higher-Order Functions

3.3. Control Structures - For Expressions

Retype, compile, and run the following Java programs using the for statement:

public class For1 {
  public static void main (String[] args) {
    for (int i = 0; i < args.length; i++) {
      System.out.println (args[i]);
    }
  }
}

public class For2 {
  public static void main (String[] args) {
    for (int i = 0; i < args.length; i++) {
      String arg = args[i];
      System.out.println (arg);
    }
  }
}

public class For3 {
  public static void main (String[] args) {
    for (String arg : args) {
      System.out.println (arg);
    }
  }
}

Run them using several arguments on the command line, e.g.,

$ java For3 the rain in spain
the
rain
in
spain

Note that the first two programs use the traditional for statement as found in the C programming language. The last program uses an "enhanced" for statement that works on any data structure implementing the correct iteration interfaces.

These Java programs correspond to the next three Python programs. In particular, the Python for statement corresponds to Java's "enhanced" for statement not the traditional for statement from the C programming language.

import sys

i = 1
while i < len (sys.argv):
    print (sys.argv[i])
    i = i + 1

import sys

i = 1
while i < len (sys.argv):
    arg = sys.argv[i]
    print (arg)
    i = i + 1

import sys

for arg in sys.argv[1:]:
    print (arg)

Run them using, e.g.,

$ python3 for3.py the rain in spain
the
rain
in
spain

Scala's for expression can be used like Java's "enhanced" for statement or Python's for statement. Try this code in the Scala console.

for x <- List (1, 2, 3, 4) do println (x)

The numbers 1 to 4 are printed as a side-effect (try it!).

But Scala's for expression is an expression, so what type does it have? Find out by running this in the Scala console:

val result = for x <- List (1, 2, 3, 4) do println (x)

This type means that there is no interesting value, so the for expression is behaving like the Java and Python versions.

But if we add the yield keyword, we can get useful values out of a Scala for expression. Try running this code in the Scala console:

val result = for x <- List (1, 2, 3, 4) yield x

What is the type of result?

We can "yield" other expressions. Try running each of these expressions in the Scala console:

val result = for x <- List (1, 2, 3, 4) yield 2 * x

val result = for x <- List (1, 2, 3, 4) yield s"${x} potato"

val result = for x <- List (1, 2, 3, 4) yield List (2 * x)

Note that the type of result in each case has the form List[A] where A is the type of the expression after yield. I.e., x is taking values from List (1,2,3,4) : List[Int] so x has type Int. Then the expression (x + " potato") has type String, so the type of result is List[String] for the second for expression above.

Now look at the following Scala code and figure out what type xs and result have. Try running the code to confirm your answer.

val result = for xs <- List (List (1, 2, 3, 4), List (5, 6, 7), List (8), List ()) yield xs

We can perform a nested loop over a list of lists without yield like this:

val result = for xs <- List (List (1, 2, 3, 4), List (5, 6, 7), List (8), List ()) do { for x <- xs do println (x) }

or with indentation:

val result = for xs <- List (List (1, 2, 3, 4), List (5, 6, 7), List (8), List ()) do
  for x <- xs do
    println (x)

When running we have, execution proceeds as normal for a loop within a loop, and variable bindings are:

outer loop: xs has value List (1, 2, 3, 4)
- x has value 1
- x has value 2
- x has value 3
- x has value 4
outer loop: xs has value List (5, 6, 7)
- x has value 5
- x has value 6
- x has value 7
outer loop: xs has value List (8)
- x has value 8
outer loop: xs has value List ()

If we want to change the elements inside the list of lists, we can. Try running this code in the Scala console:

val result = for xs <- List (List (1, 2, 3, 4), List (5, 6, 7), List (8), List ()) yield { for (x <- xs) yield 2 * x }

If we want to flatten a list of lists, we can do so using multiple arrows for one for statement:

val result = for xs <- List (List (1, 2, 3, 4), List (5, 6, 7), List (8), List ())
                  x <- xs 
             yield x

This should be treated like the previous nested loops in the sense that xs has type List[Int] and x has type Int (since its elements come from xs : List[Int]. However, the type of result is List[Int] not List[List[Int]] because the expression after yield is x which has type Int. That is, running this code produces:

result: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)

and not:

result: List[List[Int]] = List (List (1, 2, 3, 4), List (5, 6, 7), List (8), List ())

It may help to think of the Scala code:

val result = for xs <- List (List (1, 2, 3, 4), List (5, 6, 7), List (8), List ()); x <- xs yield x

as behaving like:

var result : List[Int] = List ()
for xs <- List (List (1, 2, 3, 4), List (5, 6, 7), List (8), List ()) do
  for x <- xs do
    result = result ::: List (x)

or using Java's mutable lists that add at the end of the list:

var result : java.util.List[Int] = new java.util.ArrayList[Int]
for xs <- List (List (1, 2, 3, 4), List (5, 6, 7), List (8), List ()) do
  for x <- xs do
    result.add (x)

Finally, notice that the expressions on the right-hand side of each arrow can be arbitrary, not simply a variable or list. Try running the following expressions in the Scala console:

val result = for xs <- List (List (1, 2, 3, 4), List (5, 6, 7), List (8), List ()); x <- xs.reverse yield x

val result = for xs <- List (List (1, 2, 3, 4), List (5, 6, 7), List (8), List ()).reverse; x <- xs yield x

val result = for xs <- List (List (1, 2, 3, 4), List (5, 6, 7), List (8), List ()).reverse; x <- xs.reverse yield x

val result = (for xs <- List (List (1, 2, 3, 4), List (5, 6, 7), List (8), List ()); x <- xs yield x).reverse

val result = for x <- List (1, 2, 3, 4); y <- (1 to x).toList yield y

3.4. Scala Types

What are the missing types in the following functions (work out the values of each ???)?

Confirm your answers by filling in the missing types and pasting the function definition into the Scala console.

def cons [X] (x:???, xs:???) : ??? = x::xs

def append [X] (xs:???, ys:???) : ??? = xs:::ys

def map [X,Y] (xs:???, f:???) : ??? = {
  xs match {
    case Nil   => Nil
    case y::ys => f(y) :: map(ys, f)
  }
}

def filter [X] (xs:???, f:???) : ??? = {
  xs match {
    case Nil            => Nil
    case y::ys if f (y) => y :: filter (ys, f)
    case _::ys          => filter (ys, f)
  }
}

def exists [X] (xs:???, p:???) : ??? = {
  xs match {
    case Nil       => false
    case (x :: xs) => p (x) || exists (xs, p)
  }
}

def flatten [X] (xss:???) : ??? = for (xs <- xss; x <- xs) yield x

Solution: Scala Types

4. Tail Recursion

4.1. 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

4.2. 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 xs, int low, int high) {
    int result = 0;
    while (xs != null) {
      if (low <= xs.item && xs.item <= high) {
        result = result + 1;
      }
      xs = xs.next;
    }
    return result;
  }

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

    System.out.printf ("count (..., 5, 10) = %d%n", count (list, 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

4.3. 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)

5. Lists

5.1. flatMap for Lists

What is the result of evaluating the following Scala expressions?

def repeat [X] (x:X, n:Int) : List[X] = {
  if n == 0 then 
    Nil
  else 
    x :: repeat (x, n - 1)
}

val xs:List[(Char,Int)] = List (('a', 2), ('b', 4), ('c', 8))

val ys = xs.map ((p:(Char,Int)) => repeat (p._1, p._2))

val zs = xs.flatMap ((p:(Char,Int)) => repeat (p._1, p._2))

What types do ys and zs have, and how does flatMap differ from map? Try to express flatMap using map and flatten.

Solution: flatMap for Lists

6. Solutions

6.1. Solution: Java Parametric Polymorphism Linked Lists

public class Parametric {
  static class Node<X> {
    X item;
    Node<X> next;

    public Node (X item, Node<X> next) { 
      this.item = item; 
      this.next = next; 
    }
  }

  static <X> int length (Node<X> xs) {
    if (xs == null) {
      return 0;
    } else { 
      return 1 + length (xs.next);
    }
  }

  public static void main (String[] args) {
    Node<String> list = null;
    for (int i = 0; i < args.length; i++) {
      list = new Node<String> (args[i], list);
    }
    System.out.println ("length = " + length (list));
  }
}

Sample run:

$ javac Parametric.java 

$ java Parametric the rain in spain
length = 4

6.2. Solution: Scala - Builtin Control Structures - While Loops

def printList [X] (xs:List[X]) : Unit = {
  var tmp = xs
  while tmp != Nil do
    println (tmp.head)
    tmp = tmp.tail
}

Note: Scala function definitions can often omit the return type, so the following are equivalent.

def printList (xs:List[Int]) = {
  ...
}

def printList (xs:List[Int]) : Unit = {
  ...
}

6.3. Solution: Scala - Common Higher-Order Functions

def printList (xs:List[Int]) = xs.foreach ((x:Int) => println (x))

def squares (xs:List[Int]) = xs.map ((x:Int) => x*x)

def odds (xs:List[Int]) = xs.filter ((x:Int) => (x%2 == 1))

def fiveOrGreater (xs:List[Int]) = xs.find ((x:Int) => (x >= 5))

def numFiveOrGreater (xs:List[Int]) = xs.count ((x:Int) => (x >= 5))

def existsFiveOrGreater (xs:List[Int]) = xs.exists ((x:Int) => (x >= 5))

def forallFiveOrGreater (xs:List[Int]) = xs.forall ((x:Int) => (x >= 5))

6.4. Solution: Scala Types

def cons [X] (x:X, xs:List[X]) : List[X] = x::xs

def append [X] (xs:List[X], ys:List[X]) : List[X] = xs:::ys

def map [X,Y] (xs:List[X], f:X=>Y) : List[Y] = {
  xs match {
    case Nil   => Nil
    case y::ys => f(y) :: map(ys, f)
  }
}

def filter [X] (xs:List[X], f:X=>Boolean) : List[X] = {
  xs match {
    case Nil            => Nil
    case y::ys if f (y) => y :: filter (ys, f)
    case _::ys          => filter (ys, f)
  }
}

def exists [X] (xs:List[X], p:X=>Boolean) : Boolean = {
  xs match {
    case Nil       => false
    case (x :: xs) => p (x) || exists (xs, p)
  }
}

def flatten [X] (xss:List[List[X]]) : List[X] = for xs <- xss; x <- xs yield x

6.5. 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

6.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

6.7. Solution: flatMap for Lists

def repeat [X] (x:X, n:Int) : List[X] = {
  if n == 0 then 
    Nil
  else 
    x :: repeat (x, n - 1)
}

val xs:List[(Char,Int)] = List (('a', 2), ('b', 4), ('c', 8))

val ys = xs.map ((p:(Char,Int)) => repeat (p._1, p._2))

val zs = xs.flatMap ((p:(Char,Int)) => repeat (p._1, p._2))

val zs2 = xs.map ((p:(Char,Int)) => repeat (p._1, p._2)).flatten

(zs == zs2)