# Worksheet Algebraic Data Types and Pattern Matching

## Table of Contents

## 1. Option Type

### 1.1. Maximum of a List

Write a recursive function that returns the maximum of a list of integers.

Instead of throwing an exception when the list is empty, return an `Option`

type.
That is, your function should have the following form.

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

### 1.2. Find Element

Write a higher-order function that finds the first element in a list that satisfies a given predicate (function taking an element of the list and returning a Boolean value).

Instead of throwing an exception when no such element is found, return an `Option`

type.
That is, your function should have the following form.

def find [X] (xs:List[X], p:X=>Boolean) : Option[X] = { ... }

### 1.3. Handle an Option - Pattern Matching

Consider the following Scala function.
It searches for the first `String`

in a list of `String`

references that is strictly longer than `s`

and that contains `s`

as a substring.

def oneFind (xs:List[String], s:String) : Option[String] = { xs.find ((x:String) => (x.length > s.length) && x.contains (s)) }

For example:

scala> oneFind (List ("the", "rain", "in", "spain"), "i") res1: Option[String] = Some(rain) scala> oneFind (List ("the", "rain", "in", "spain"), "in") res2: Option[String] = Some(rain) scala> oneFind (List ("the", "rain", "in", "spain"), "ain") res3: Option[String] = Some(rain) scala> oneFind (List ("the", "rain", "in", "spain"), "pain") res16: Option[String] = Some(spain) scala> oneFind (List ("the", "rain", "in", "spain"), "rain") res4: Option[String] = None

Now write a function `twoFind`

that calls `oneFind`

and then uses the result (if there is one) in a second call to `oneFind`

.

Use pattern-matching to do case analysis on the result of the first call to `oneFind`

.
Your definition of `twoFind`

should have the following form.

def twoFind (xs:List[String], s:String) : Option[String] = { ... }

Note that `twoFind`

must not have return type `Option[Option[String]]`

!

For example:

twoFind (List ("the", "rain", "in", "spain"), "i") res1: Option[String] = None scala> twoFind (List ("the", "rain", "in", "spain"), "in") res2: Option[String] = None scala> twoFind (List ("the", "rain", "in", "spain"), "n") res3: Option[String] = None scala> twoFind (List ("the", "rain", "in", "spain", "trained", "after", "a", "sprain"), "in") res4: Option[String] = Some(trained) scala> twoFind (List ("the", "rain", "in", "spain", "trained", "after", "a", "sprain"), "i") res5: Option[String] = Some(trained) scala> twoFind (List ("the", "rain", "in", "spain", "trained", "after", "a", "sprain"), "n") res6: Option[String] = Some(trained) scala> twoFind (List ("the", "rain", "in", "spain", "trained", "after", "a", "sprain"), "ain") res7: Option[String] = Some(trained) scala> twoFind (List ("the", "rain", "in", "spain", "trained", "after", "a", "sprain"), "pain") res8: Option[String] = None

### 1.4. Handle an Option - flatMap

Rewrite `twoFind`

from the previous question to use `flatMap`

for the `Option`

type instead of explicit pattern-matching.

Note: if `e`

has type `Option[A]`

and you write `e.flatMap (f)`

, then it will have type `Option[B]`

whenever `f`

has type `A=>Option[B]`

.
You may find it helpful to look at the Scala API documentation for the
`Option`

type at https://www.scala-lang.org/api/current/scala/Option.html.

Variations of `flatMap`

are idiomatic in many languages that use `Option`

types.

## 2. Classes in Scala

### 2.1. Java Translation

Translate the following Java class definition into a corresponding Scala class definition.
You will need a companion object definition to model the `static`

components.

In order to definition the Scala class and object at the same time in the Scala REPL, you must enter `:paste`

, paste your definitions **together**, and then press control-D.

class Counter { private static int numCounters = 0; final int id; int count; Counter (int initial) { this.id = numCounters; this.count = initial; numCounters++; } static int getNumCounters () { return numCounters; } int getId () { return this.id; } int getNextCount () { return this.count++; } }

## 3. Algebraic Data Types via Case classes in Scala

### 3.1. MyList Case Class

Define your own `MyList`

class in Scala (as in the slides).

Now implement the following functions:

enum MyList[+X] { ... } import MyList._ def length [X] (xs:MyList[X]) : Int = { ... } def toList [X] (xs:MyList[X]) : List[X] = { ... } def fromList [X] (xs:List[X]) : MyList[X] = { ... } def append [X] (xs:MyList[X], ys:MyList[X]) : MyList[X] = { ... } def map [X,Y] (xs:MyList[X], f:X=>Y) : MyList[Y] = { ... }

### 3.2. Binary Tree Case Class

Define your own `Tree`

class for binary trees in Scala (as in the slides).

Now implement the following functions:

enum Tree[+X] { case Leaf case Node(l:Tree[X], c:X, r:Tree[X]) } import Tree.{Leaf,Node} val tree1:Tree[Int] = Leaf val tree2:Tree[Int] = Node (Leaf, 5, Leaf) val tree3:Tree[Int] = Node (Node (Leaf, 2, Leaf), 3, Node (Leaf, 4, Leaf)) // Find the size of a binary tree. Leaves have size zero here. def size [X] (t:Tree[X]) : Int = { ... } // Insert a number into a sorted binary tree. def insert [X] (x:X, t:Tree[X], lt:(X,X)=>Boolean) : Tree[X] = { ... } // Put the elements of the tree into a list using an in-order traversal. def inorder [X] (t:Tree[X]) : List[X] = { ... }

## 4. Solutions

### 4.1. Solution: Maximum of a List

def maximum (xs:List[Int]) : Option[Int] = { xs match { case Nil => None case y::ys => maximum (ys) match { case None => Some (y) case Some (z) => Some (y max z) } } }

Suppose we start with maximum (List(11,31,21)). Computation goes as follows:

maximum (List(11,31,21)) => maximum (List(31,21)) match [with y=11] { ... } => (maximum (List(21)) match [with y=31] {...}) match [with y=11] { ... } => ((maximum (List()) match [with y=21] {...}) match [with y=31] {...}) match [with y=11] { ... } => ((None match [with y=21] {...}) match [with y=31] {...}) match [with y=11] { ... } => (Some(21) match [with y=31] {...}) match [with y=11] { ... } => Some(31 max 21) match [with y=11] { ... } => Some(31) match [with y=11] { ... } => Some(11 max 31) => Some(31)

Itâ€™s actually easier to understand if you starting at Nil by running on progressively longer lists:

maximum(List()) => None maximum(List(21)) => maximum(List()) match {...} => None match {...} => Some(21) maximum(List(31,21)) => maximum(List(21)) match {...} => Some(21) match {...} => Some(31 max 21) => Some(31) maximum(List(11,31,21)) => maximum(List(31,21)) match {...} => Some(31) match {...} => Some(11 max 31) => Some(31)

Recall that match is simply short-hand for if-else and is evaluated left to right. So the definition above is equivalent to:

def maximum (xs:List[Int]) : Option[Int] = { if (xs == Nil) { //case Nil None } else { // case y::ys val y = xs.head val ys = xs.tail val zoption = maximum (ys) if (zoption == None) { // case None Some (y) } else { // case Some(z) val z = zoption.get Some (y max z) } } }

### 4.2. Solution: Find Element

def find [X] (xs:List[X], p:X=>Boolean) : Option[X] = { xs match { case Nil => None case y::ys if p (y) => Some (y) case _::ys => find (ys, p) } }

This one is easier since tail recursive:

def p = (x:Int) => (x==5) find(List(11,5,21), p) => find(List(5,21), p) => Some(5) find(List(11,21), p) => find(List(21), p) => None

### 4.3. Solution: Handle an Option - Pattern Matching

def oneFind (xs:List[String], s:String) : Option[String] = { xs.find ((x:String) => (x.length > s.length) && x.contains (s)) } def twoFind (xs:List[String], s:String) : Option[String] = { oneFind (xs, s) match { case None => None case Some (t) => oneFind (xs, t) } }

### 4.4. Solution: Handle an Option - flatMap

def oneFind (xs:List[String], s:String) : Option[String] = { xs.find ((x:String) => (x.length > s.length) && x.contains (s)) } def twoFind (xs:List[String], s:String) : Option[String] = { oneFind (xs, s).flatMap ((t:String) => oneFind (xs, t)) }

### 4.5. Solution: Classes - Java Translation

object Counter: private var numCounters = 0 def getNumCounters : Int = numCounters def incNumCounters : Unit = numCounters = numCounters + 1 class Counter (initial:Int): private val id:Int = Counter.getNumCounters private var count:Int = initial Counter.incNumCounters def getId () : Int = id def getNextCount () : Int = { val tmp = count; count = count + 1; tmp }

### 4.6. Solution: MyList Case Class

enum MyList[+X]: case MyNil case MyCons(head:X, tail:MyList[X]) import MyList.* def length [X] (xs:MyList[X]) : Int = xs match case MyNil => 0 case MyCons (_, ys) => 1 + length (ys) def toList [X] (xs:MyList[X]) : List[X] = xs match case MyNil => Nil case MyCons (y, ys) => y::toList(ys) def fromList [X] (xs:List[X]) : MyList[X] = xs match case Nil => MyNil case y::ys => MyCons (y, fromList (ys)) def append [X] (xs:MyList[X], ys:MyList[X]) : MyList[X] = xs match case MyNil => ys case MyCons (z, zs) => MyCons (z, append (zs, ys)) def map [X,Y] (xs:MyList[X], f:X=>Y) : MyList[Y] = xs match case MyNil => MyNil case MyCons (y, ys) => MyCons (f (y), map (ys, f)) val xs = MyCons(11, MyCons(21, MyCons(31, MyNil))) val len = length (xs)

### 4.7. Solution: Binary Tree Case Class

enum Tree[+X]: case Leaf case Node(l:Tree[X], c:X, r:Tree[X]) import Tree.* val tree1:Tree[Int] = Leaf val tree2:Tree[Int] = Node (Leaf, 5, Leaf) val tree3:Tree[Int] = Node (Node (Leaf, 2, Leaf), 3, Node (Leaf, 4, Leaf)) // Find the size of a binary tree. Leaves have size zero here. def size [X] (t:Tree[X]) : Int = t match case Leaf => 0 case Node (t1, _, t2) => size (t1) + 1 + size (t2) // Insert a number into a sorted binary tree. def insert [X] (x:X, t:Tree[X], lt:(X,X)=>Boolean) : Tree[X] = t match case Leaf => Node (Leaf, x, Leaf) case Node (t1, c, t2) if (lt (x, c)) => Node (insert (x, t1, lt), c, t2) case Node (t1, c, t2) if (lt (c, x)) => Node (t1, c, insert (x, t2, lt)) case Node (t1, c, t2) => Node (t1, c, t2) // Put the elements of the tree into a list using an in-order traversal. def inorder [X] (t:Tree[X]) : List[X] = t match case Leaf => Nil case Node (t1, c, t2) => inorder (t1) ::: List (c) ::: inorder (t2)