// Task 1 

abstract class Tree
case class Leaf(x: Int) extends Tree
case class Node(left: Tree, right: Tree) extends Tree 

def mirror(t: Tree) : Tree = t match {
  case Leaf(n) => Leaf(n)
  case Node(l, r) => Node(mirror(r), mirror(l))
}

def sum_tree(t: Tree) : Int = t match {
  case Leaf(n) => n
  case Node(l, r) => sum_tree(l) + sum_tree(r)
}

// Task 2

// version with default argument
def remdups(xs: List[Int], acc: Set[Int] = Set()) : List[Int] = xs match {
  case Nil => Nil
  case x::xs => if (acc.contains(x)) remdups(xs, acc + x)
                else x::remdups(xs, acc + x)
}

//version with auxiliary function
def remdups(xs: List[Int]) = {
  def aux(xs: List[Int], acc: Set[Int]) : List[Int] = xs match {
    case Nil => Nil
    case x::xs => if (acc.contains(x)) aux(xs, acc + x)
                  else x::aux(xs, acc + x)
  }
  aux(xs, Set())
}


// Task 3
def indexOfOption(xs: List[Int], e: Int) : Option[Int] = xs match {
  case Nil => None
  case x::xs => if (x == e) Some(0)
                else indexOfOption(xs, e).map(_ + 1)
}

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


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

def height(t: Tree) : Int = t match {
  case Leaf(_) => 0
  case Node(l, r) => 1 + List(height(l), height(r)).max
}

def balance(t: Tree) : Tree = t match {
  case Leaf(n) => Leaf(n)
  case Node(l, r) if (height(l) - height(r)).abs <= 1 
    => Node(l, r)
  case Node(l, r : Node) if height(l) < height(r) => 
    balance(Node(Node(l, r.left), r.right))
  case Node(l : Node, r) if height(l) > height(r) => 
    balance(Node(l.left, Node(l.right, r)))
}

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

// Task 5 (fold, hard)

def fold(xs: List[Int], f: (Int, Int) => Int, u: Int) : Int = xs match {
  case Nil => u
  case x::xs => f(x, fold(xs, f, u))
}


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