Skip to content

Instantly share code, notes, and snippets.

@huynhjl
Created December 27, 2011 18:16
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save huynhjl/1524670 to your computer and use it in GitHub Desktop.
List foldLeft implementations
object C extends App {
def time[F](f: => F) = {
val t0 = System.nanoTime
val ans = f
printf("Elapsed: %.3f\n",1e-9*(System.nanoTime-t0))
ans
}
def lots[F](n: Int, f: => F): F = if (n <= 1) f else { f; lots(n-1,f) }
def bench[F](what:String, n:Int, f: => F) = {
println(what + ": warming...")
lots(n, f)
time(what, f)
}
def foldLeft[A, B](list: List[A], z: B)(f: (B, A) => B): B = {
var acc = z
var these = list
while (!these.isEmpty) {
acc = f(acc, these.head)
these = these.tail
}
acc
}
@annotation.tailrec
def foldLeft2[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
list match {
case x :: xs => foldLeft2(xs, f(x, acc))(f)
case Nil => acc
}
}
@annotation.tailrec
final def foldLeft3[T, U](list: List[T], acc: U)(f: (T, U) => U):
U = if (list eq Nil) acc else foldLeft3(list.tail, f(list.head, acc))(f)
val size = 500000
val list = List.fill(size)(1)
val warm = 20
val n = 2
val f = (a:Int, b:Int) => a * b
bench("tailrec match foldLeft2", warm, lots(n, foldLeft2(list, 0)(f)))
bench("tailrec if/else foldLeft3", warm, lots(n, foldLeft3(list, 0)(f)))
bench("lib foldLeft", warm, lots(n, list.foldLeft(0)(f)))
bench("pulled-in foldLeft", warm, lots(n, foldLeft(list, 0)(f)))
}
@huynhjl
Copy link
Author

huynhjl commented Dec 27, 2011

Timings on 2.9.1 compiled with -optimized (ran under sbt) are:
[info] Running C
tailrec match foldLeft2: warming...
Elapsed: 0.024
tailrec if/else foldLeft3: warming...
Elapsed: 0.045
lib foldLeft: warming...
Elapsed: 0.068
pulled-in foldLeft: warming...
Elapsed: 0.069

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment