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.

Lists

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

Classes in Scala

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++;
  }
}

Solution: Classes - Java Translation

Algebraic Data Types via Case classes in Scala

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] = {
    ...
  }

Solution: MyList Case Class

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] = {
  ...
}

Solution: Binary Tree Case Class

Solutions

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)

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 }

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)

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)