Skip to content

Instantly share code, notes, and snippets.

@jixu
Last active August 29, 2015 14:01
Show Gist options
  • Save jixu/3cb125bbf623e4b2ab0a to your computer and use it in GitHub Desktop.
Save jixu/3cb125bbf623e4b2ab0a to your computer and use it in GitHub Desktop.
3 versions of list insertion
object ListInsertion extends App {
/**
* non tail-recursive version
*/
def insert1[T](l: List[T], v: T)(implicit ord: Ordering[T]): List[T] = l match {
case List() => List(v)
case x :: xs =>
if (ord.lt(x, v)) x :: insert1(xs, v)
else v :: l
}
/**
* tail-recursive with data accumulator.
*/
def insert2[T](l: List[T], v: T)(implicit ord: Ordering[T]): List[T] = {
def concatReversePrefix(l: List[T], prefix: List[T]): List[T] = prefix match {
case List() => l
case x :: xs => concatReversePrefix(x :: l, xs)
}
def insertRec(l: List[T], prefix: List[T]): List[T] = l match {
case List() => concatReversePrefix(List(v), prefix)
case x :: xs =>
if (ord.lt(x, v)) insertRec(xs, x :: prefix)
else concatReversePrefix(v :: l, prefix)
}
insertRec(l, List())
}
/**
* tail-recursive with function accumulator.
*/
def insert3[T](l: List[T], v: T)(implicit ord: Ordering[T]): List[T] = {
def insertRec(l: List[T], f: (List[T]) => List[T]): List[T] = l match {
case List() => f(List(v))
case x :: xs =>
if (ord.lt(x, v)) insertRec(xs, {l => f(x :: l)})
else f(v :: l)
}
insertRec(l, {l => l})
}
val l = List(1, 2, 4, 5)
val v = 3
val ll = List(1, 2, 3, 4, 5)
assert(insert1(l, v) == ll)
assert(insert2(l, v) == ll)
assert(insert3(l, v) == ll)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment