def toRoman(num: Int): String = {
  def convertDigit(ten: String, five: String, one: String) = (num:Int) => (num%10) match {
    case 9 => one + ten
    case d if d>=5 => five + one*(d-5)
    case 4 => one + five
    case d => one*d
  }

  val units = convertDigit("X","V","I")
  val tens = convertDigit("C","L","X")
  val hundreds = convertDigit("M","D","C")
  val thousands = convertDigit("","","M")

  thousands(num/1000) + hundreds(num/100) + tens(num/10) + units(num)
}

def iterate[A,B](f: (A, B) => A, initial_value: A, L: List[B]): A = {
  def iter(a: A, L: List[B]) : A = L match {
    case Nil => a
    case x::xs => iter(f(a, x), xs)
  }

  iter(initial_value, L)
}

def sum(L: List[Int]) = iterate((x: Int, y: Int) => x + y, 0, L)
def sum(L: List[Int]) = iterate((_: Int) + (_: Int), 0, L)

def splitAt[A](L: List[A], n: Int): (List[A], List[A]) = (L, n) match {
  case (L, 0) => (Nil, L)
  case (Nil, _) => (Nil, Nil)
  case (x::xs, n) => splitAt(xs, n - 1) match {
    case (left, right) => (x::left, right)
  }

}

def countChange(amount: Int, coins: List[Int]): Int = (amount, coins) match {
  case (0, _) => 1
  case (_, Nil) => 0
  case (amount, x::xs) => {
    val withx = if (amount >= x) countChange(amount - x, coins) else 0
    val withoutx = countChange(amount, xs)

    withx + withoutx
  }
}