Skip to content

Instantly share code, notes, and snippets.

@trane
Created January 26, 2015 20:50
Show Gist options
  • Save trane/605a981838db663ebe7f to your computer and use it in GitHub Desktop.
Save trane/605a981838db663ebe7f to your computer and use it in GitHub Desktop.
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment