Assignment_04/src/main/scala/Main.scala

   1 object Main {
   2
   3   // Question 1: Expressions.
   4   sealed abstract class Expr
   5   case class Number(n: Int) extends Expr
   6   case class Sum(e1: Expr, e2: Expr) extends Expr
   7   case class Product(e1: Expr, e2: Expr) extends Expr
   8
   9   def eval(e: Expr): Int = e match {
  10     case Number(n) => n
  11     case Sum(e1, e2) => eval(e1) + eval(e2)
  12     case Product(e1, e2) => eval(e1) * eval(e2)
  13   }
  14
  15   def showFromProduct(e: Expr) : String = e match {
  16     case Sum(e1, e2) => s"(${show(e1)} + ${show(e2)})"
  17     case e => show(e)
  18   }
  19
  20   def show(e: Expr): String = e match {
  21     case Number(n) => n.toString()
  22     case Sum(e1, e2) => s"${show(e1)} + ${show(e2)}"
  23     case Product(e1, e2) => s"${showFromProduct(e1)} * ${showFromProduct(e2)}"
  24   }
  25
  26   // Question 2: Trees.
  27   sealed abstract class BinaryTree
  28   case class Leaf(value: Int) extends BinaryTree
  29   case class Node(left: BinaryTree, right: BinaryTree) extends BinaryTree
  30
  31   def sum(tree: BinaryTree): Int = tree match {
  32     case Leaf(v) => v
  33     case Node(l, r) => sum(l) + sum(r)
  34   }
  35
  36   def min(a: Int, b: Int): Int = if (a < b) a else b
  37   def minimum(tree: BinaryTree): Int = tree match {
  38     case Leaf(v) => v
  39     case Node(l, r) => min(minimum(l), minimum(r))
  40   }
  41
  42   // Question 3: Lists functions.
  43   def last[T](l: List[T]): T = l match {
  44     case Nil => throw new Exception("empty list")
  45     case x :: Nil => x
  46     case x :: xs => last(xs)
  47   }
  48   def init[T](l: List[T]): List[T] =  l match {
  49     case Nil => Nil
  50     case x :: Nil => Nil
  51     case x :: xs => x :: init(xs)
  52   }
  53   def concat[T](l1: List[T])(l2: List[T]): List[T] = l1 match {
  54     case Nil => l2
  55     case x :: xs => x :: concat(xs)(l2)
  56   }
  57   def reverse[T](l: List[T]): List[T] = l match {
  58     case Nil => Nil
  59     case x :: xs => concat(reverse(xs))(List(x))
  60   }
  61   def take[T](l: List[T])(n: Int): List[T] = l match {
  62     case Nil => Nil
  63     case _ if n == 0 => Nil
  64     case x :: xs => x :: take(xs)(n - 1)
  65   }
  66   def drop[T](l: List[T])(n: Int): List[T] = l match {
  67     case Nil => Nil
  68     case xs if n == 0 => xs
  69     case x :: xs => drop(xs)(n - 1)
  70   }
  71   def apply[T](l: List[T])(n: Int): T = l match {
  72     case Nil => throw new Exception("out of bounds")
  73     case x :: xs => if (n == 0) x else apply(xs)(n - 1)
  74   }
  75
  76   // Question 4: Predicates on lists.
  77   def any[T](l: List[T])(p: T => Boolean): Boolean = l match {
  78     case Nil => false
  79     case x :: xs => if (p(x)) true else any(xs)(p)
  80   }
  81   def every[T](l: List[T])(p: T => Boolean): Boolean = l match {
  82     case Nil => true
  83     case x :: xs => if (p(x)) every(xs)(p) else false
  84   }
  85
  86   def main(args: Array[String]) = {
  87     println("Assignment 4")
  88     println("Question 1: Expressions")
  89
  90     val expr0 = Sum(Product(Number(2), Number(3)), Number(4))
  91     println(s"Expr0: ${show(expr0)}")
  92     assert(eval(expr0) == 10)
  93
  94     val expr1 = Product(Number(4), Number(12))
  95     println(s"Expr1: ${show(expr1)}")
  96     assert(eval(expr1) == 48)
  97
  98     val expr2 = Product(Sum(Number(2), Number(3)), Number(4))
  99     println(s"Expr2: ${show(expr2)}")
 100     assert(eval(expr2) == 20)
 101
 102     val expr3 = Product(Number(2), Sum(Number(3), Number(4)))
 103     println(s"Expr3: ${show(expr3)}")
 104     assert(eval(expr3) == 14)
 105     println()
 106
 107
 108     println("Question 2: Tree")
 109     val t = Node(Node(Leaf(4), Leaf(8)), Leaf(2))
 110     println(s"minimum($t): ${minimum(t)}")
 111     assert(minimum(t) == 2)
 112     val t2 = Node(Leaf(8), Node(Leaf(2), Leaf(1)))
 113     println(s"minimum($t2): ${minimum(t2)}")
 114     assert(minimum(t2) == 1)
 115     println()
 116
 117
 118     println("Question 3: Lists functions")
 119
 120     val l1 = List(2, 3, 1, 4, 2, 9)
 121     val l2 = List(8)
 122     val l3 : List[Int] = Nil
 123
 124     println(s"last($l1): ${last(l1)}")
 125     println(s"last($l2): ${last(l2)}")
 126
 127     println(s"init($l1): ${init(l1)}")
 128     println(s"init($l2): ${init(l2)}")
 129     println(s"init($l3): ${init(l3)}")
 130
 131     println(s"concat(concat($l1)($l2))($l3): ${concat(concat(l1)(l2))(l3)}")
 132
 133     println(s"reverse($l1): ${reverse(l1)}")
 134     println(s"reverse($l2): ${reverse(l2)}")
 135     println(s"reverse($l3): ${reverse(l3)}")
 136
 137     println(s"take($l1)(3): ${take(l1)(3)}")
 138     println(s"take($l1)(6): ${take(l1)(6)}")
 139     println(s"take($l1)(10): ${take(l1)(10)}")
 140
 141     println(s"drop($l1)(3): ${drop(l1)(3)}")
 142     println(s"drop($l1)(6): ${drop(l1)(6)}")
 143     println(s"drop($l1)(10): ${drop(l1)(10)}")
 144
 145     println(s"apply($l1)(0): ${apply(l1)(0)}")
 146     println(s"apply($l1)(3): ${apply(l1)(3)}")
 147     println(s"apply($l1)(5): ${apply(l1)(5)}")
 148     println()
 149
 150
 151     println("Question 4: Predicates on lists")
 152     println(s"any($l1)(_ == 4): ${any(l1)(_ == 4)}")
 153     println(s"any($l1)(_ == 13): ${any(l1)(_ == 13)}")
 154
 155     println(s"every($l1)(_ < 4): ${every(l1)(_ < 4)}")
 156     println(s"every($l1)(_ < 13): ${every(l1)(_ < 13)}")
 157   }
 158 }