--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/wsheets/wsh03.scala	Thu Dec 08 17:53:08 2022 +0000
@@ -0,0 +1,78 @@
+
+// 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)
\ No newline at end of file