gistfile1.scala

def merge[A](t: (List[A], List[A]))(implicit p: (A, A) => Boolean): List[A] = {
  t match {
    case (as, Nil) => as
    case (Nil, bs) => bs
    case (a :: as, b :: bs) => if (p(a, b)) a :: merge((as, t._2))
    else b :: merge((t._1, bs))
  }
}

def split[A](s: List[A]): (List[A], List[A]) =
  s.splitAt(s.size/2)

def mergeSort[A](s: List[A])(implicit p: (A, A) => Boolean): List[A] =
  if (s.size < 2) s
  else {
    val (l, r) = split(s)
    merge((mergeSort(l), mergeSort(r))).reverse
  }

implicit def lt[A](a: A, b: A)(implicit ord: Ordering[A]) = ord.lt(a, b)
mergeSort(List(4, 8, 3, 2, 1, 6, 7, 5))
lazy val fibs: Stream[BigInt] = 0 #:: 1 #:: ((fibs zip fibs.tail) map (t => t._1 + t._2))
fibs.take(5).last.toString().size

def quicksort[A](l: IndexedSeq[A])(implicit ord: Ordering[A]): IndexedSeq[A] = {
  if (l.isEmpty) l
  else {
    var smallerSorted = quicksort(for(a <- l.tail; if ord.lt(a, l.head)) yield a)
    var biggerSorted = quicksort(for(a <- l.tail; if ord.gteq(a, l.head)) yield a)
    (smallerSorted :+ l.head) ++ biggerSorted
  }
}

quicksort(Vector(10,2,5,3,1,6,7,4,2,3,4,8,9))
quicksort(Vector('a', 'z', 'd', 'e', 'A', 'E'))
quicksort(Vector("hello", "world", "and", "other", "planets"))

def maximumOption[A](l: IndexedSeq[A])(implicit ord: Ordering[A]): Option[A] = {
  if (l.size <= 1) l.headOption
  else Some(ord.max(l.head, maximumOption(l.tail).get))
}

def maximum[A](l: IndexedSeq[A])(implicit ord: Ordering[A]): A = {
  if (l.size == 1) l.head
  else ord.max(l.head, maximum(l.tail))
}

def maximum2[A](l: IndexedSeq[A])(implicit ord: Ordering[A]): A = l match {
  case IndexedSeq() => throw new Exception("empty list")
  case IndexedSeq(a) => a
  case a +: as => ord.max(a, maximum2(as))
}

maximum(Vector(1,2,3,4,5,6,0))
maximum(Vector[Int](1,2,9))
maximum2(Vector(1,2,3,4,5,6,0))
maximum(Vector(Some(1), Some(2), Some(3), None))
maximum(Vector[Option[Int]](None))

def replicate[A](times: Int)(value: A): List[A] =
  if (times < 1) List()
  else value :: replicate(times - 1)(value)

replicate (5) ('a')

def take[A](num: Int)(l: List[A]): List[A] =
  if (num < 1) List()
  else l.head :: take(num-1)(l.tail)

take (3) (fibs.take(5).toList)