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