1 

     2 // Task 1 

     3 

     4 abstract class Tree

     5 case class Leaf(x: Int) extends Tree

     6 case class Node(left: Tree, right: Tree) extends Tree 

     7 

     8 def mirror(t: Tree) : Tree = t match {

     9   case Leaf(n) => Leaf(n)

    10   case Node(l, r) => Node(mirror(r), mirror(l))

    11 }

    12 

    13 def sum_tree(t: Tree) : Int = t match {

    14   case Leaf(n) => n

    15   case Node(l, r) => sum_tree(l) + sum_tree(r)

    16 }

    17 

    18 // Task 2

    19 

    20 // version with default argument

    21 def remdups(xs: List[Int], acc: Set[Int] = Set()) : List[Int] = xs match {

    22   case Nil => Nil

    23   case x::xs => if (acc.contains(x)) remdups(xs, acc + x)

    24                 else x::remdups(xs, acc + x)

    25 }

    26 

    27 //version with auxiliary function

    28 def remdups(xs: List[Int]) = {

    29   def aux(xs: List[Int], acc: Set[Int]) : List[Int] = xs match {

    30     case Nil => Nil

    31     case x::xs => if (acc.contains(x)) aux(xs, acc + x)

    32                   else x::aux(xs, acc + x)

    33   }

    34   aux(xs, Set())

    35 }

    36 

    37 

    38 // Task 3

    39 def indexOfOption(xs: List[Int], e: Int) : Option[Int] = xs match {

    40   case Nil => None

    41   case x::xs => if (x == e) Some(0)

    42                 else indexOfOption(xs, e).map(_ + 1)

    43 }

    44 

    45 indexOfOption(List(1,2,3,4,5,6), 7) // => None

    46 indexOfOption(List(1,2,3,4,5,6), 4) // => Some(3)

    47 indexOfOption(List(1,2,3,4,3,6), 3) // => Some(2)

    48 

    49 

    50 // Task 4 (Pattern Matching, If-Guards, hard)

    51 

    52 def height(t: Tree) : Int = t match {

    53   case Leaf(_) => 0

    54   case Node(l, r) => 1 + List(height(l), height(r)).max

    55 }

    56 

    57 def balance(t: Tree) : Tree = t match {

    58   case Leaf(n) => Leaf(n)

    59   case Node(l, r) if (height(l) - height(r)).abs <= 1 

    60     => Node(l, r)

    61   case Node(l, r : Node) if height(l) < height(r) => 

    62     balance(Node(Node(l, r.left), r.right))

    63   case Node(l : Node, r) if height(l) > height(r) => 

    64     balance(Node(l.left, Node(l.right, r)))

    65 }

    66 

    67 balance(Node(Leaf(1), Node(Leaf(2), Node(Leaf(3), Leaf(4)))))

    68 

    69 // Task 5 (fold, hard)

    70 

    71 def fold(xs: List[Int], f: (Int, Int) => Int, u: Int) : Int = xs match {

    72   case Nil => u

    73   case x::xs => f(x, fold(xs, f, u))

    74 }

    75 

    76 

    77 def sum(xs: List[Int]) = fold(xs, _ + _, 0)

    78 def prod(xs: List[Int]) = fold(xs, _ * _, 1)