import scala.collection.immutable.ListMap /* Part 2 */ def incr(x: Int): Int = x + 1 def double(x: Int): Int = x + x def square(x: Int): Int = x * x def factorial(n: Int): Int = if (n == 0) {1} else {n * factorial(n-1)} def power(x: Int, n: Int): Int = if (n == 0) {1} else {x * power(x,n-1)} def factorial1(n: Int): Int = { val m = n-1 ; if (n == 0) {1} else {n * factorial1(m)} } def factorial2(n: Int): Int = { val m = n-1; if (n == 0) {1} else {n * factorial2(m)} } def factorial3(n: Int): Int = { val m = n-1; if (n == 0) { return 1; } else { return n * factorial3(m); } } /* Exercise 1 */ def p(x: Int, y:Int): Int = x*x + 2*x*y + y*y*y - 1 /* Exercise 2 */ def sum(n: Int): Int = if (n == 0) { 0 } else { n + sum(n-1) } /* Part 3 */ /* Exercise 3 */ def cycle(p:(Int,Int,Int)): (Int,Int,Int) = (p._2,p._3,p._1) /* Part 4 */ def nameFromNum(presidentNum: Int): String = presidentNum match { case 41 => "George H. W. Bush" case 42 => "Bill Clinton" case 43 => "George W. Bush" case 44 => "Barack Obama" } def numFromName(presidentName: String): Int = presidentName match { case "George H. W. Bush" => 41 case "Bill Clinton" => 42 case "George W. Bush" => 43 case "Barack Obama" => 44 } /* Exercise 4 */ def suffix(n: Int): String = { (n % 100) match { case 11 => "th" case 12 => "th" case 13 => "th" case _ => (n % 10) match { case 1 => "st" case 2 => "nd" case 3 => "rd" case _ => "th" } } } abstract class Colour case class Red() extends Colour case class Green() extends Colour case class Blue() extends Colour /* Exercise 5 */ def favouriteColour(c: Colour): Boolean = c match { case Red() => false; case Blue() => true; case Green() => false; } abstract class Shape case class Circle(r: Double, x: Double, y: Double) extends Shape case class Rectangle(llx: Double, lly: Double, w:Double, h:Double) extends Shape def center(s: Shape): (Double,Double) = s match { case Rectangle(llx,lly,w,h) => (llx+w/2, lly+h/2) case Circle(r,x,y) => (x,y) } /* Exercise 6 */ def boundingBox(s: Shape): Rectangle = s match { case Rectangle(lrx, lry, w, h) => Rectangle(lrx, lry, w, h) case Circle(r, x, y) => Rectangle(r - x, r - y, 2 * r, 2 * r) } /* Exercise 7 */ def intervalOverlap(x1: Double, x2: Double,y1: Double, y2: Double): Boolean = { y1 <= x2 && x1 <= y2 } def mayOverlap(s1: Shape, s2: Shape) = { val bb1 = boundingBox(s1); val bb2 = boundingBox(s2); (bb1, bb2) match { case (Rectangle(llx1, lly1, w1, h1), Rectangle(llx2, lly2, w2, h2)) => intervalOverlap(llx1,llx1+w1,llx2,llx2+w2) && intervalOverlap(lly1,lly1+h1,lly2,lly2+h2) } } /* Part 5 */ val anonIncr = {x: Int => x+1} // anonymous version of incr val anonAdd = {x: Int => {y: Int => x + y}} /* Exercise 8 */ def compose1[A, B, C](f: A => B, g: B => C)(x:A) = g(f(x)) /* Exercise 9 */ def compose[A, B, C](f: A => B, g: B => C) = {x:A => g(f(x))} /* Exercise 10 */ def e1 = {x: Int => x.toString} def e2 = {x: String => true} def isEmpty[A](l: List[A]) = l match { case Nil => true case x :: y => false } /* Exercise 11 */ def map[A, B](f: A => B, l: List[A]): List[B] = l match { case Nil => Nil case x :: xs => f(x) :: map(f,xs) } /* Exercise 12 */ def filter[A](f: A => Boolean, l: List[A]): List[A] = l match { case Nil => Nil case x :: xs => if (f(x)) {x :: filter(f,xs)} else {filter(f,xs)} } /* Exercise 13 */ def reverse[A](l: List[A]): List[A] = l match { case Nil => Nil case x :: xs => reverse(xs) :+ x } /* alternative, faster solution */ def fast_reverse[A](l: List[A]): List[A] = { def go[A](l: List[A], rl: List[A]): List[A] = l match { case Nil => rl case x :: xs => go(xs,x::rl) } go(l,Nil) } /* Part 6 */ def empty[K,V]: List[(K,V)] = List() /* Exercise 14 */ def lookup[K, V](m: List[(K, V)], k: K): V = m match { case (k2,v)::m2 => if (k == k2) {v} else {lookup(m2,k)} case Nil => sys.error("Match failure") } /* Exercise 15 */ def update[K, V](m: List[(K, V)], k: K, v: V): List[(K, V)] = m match { case Nil => List((k,v)) case (k2,v2)::m2 => if (k == k2) { (k,v)::m2 } else { (k2,v2)::update(m2,k,v) } } /* Exercise 16 */ def keys[K,V](m: List[(K,V)]): List[K] = map({x:(K,V) => x._1},m) /* Exercise 17 */ val presidentListMap: ListMap[Int,String] = ListMap( 41 -> "George H. W. Bush", 42 -> "Bill Clinton", 43 -> "George W. Bush", 44 -> "Barack Obama") /* Exercise 18 */ def m0_withUpdate = ListMap(1 -> "a", 2 -> "b") /* Exercise 19 */ def list2map[K,V](l: List[(K,V)]): ListMap[K,V] = l match { case Nil => ListMap[K,V]() case (k,v) :: m => list2map(m) + (k -> v) } /* Exercise 20 */ def election(votes: List[String]): ListMap[String,Int] = votes match { case Nil => ListMap[String,Int]() case k :: l => { val m = election(l) if (m.contains(k)) { m + (k -> (m(k)+1)) } else { m + (k -> 1) } } }