# Worksheet Functional Programming

## Table of Contents

- 1. Questions and Completion
- 2. Java
- 3. Scala - Functional Programming
- 4. Tail Recursion
- 5. Lists
- 6. Solutions
- 6.1. Solution: Java Parametric Polymorphism Linked Lists
- 6.2. Solution: Scala - Builtin Control Structures - While Loops
- 6.3. Solution: Scala - Common Higher-Order Functions
- 6.4. Solution: Scala Types
- 6.5. Solution: Scala - Looping in Scala with a Function
- 6.6. Solution: Scala - Counting Values
- 6.7. Solution: flatMap for Lists

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

## 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 ... }

### 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!)

### 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

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

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

### 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`

.

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