Skip to content

Instantly share code, notes, and snippets.

@netslow
Created April 15, 2011 17:45
Show Gist options
  • Save netslow/922115 to your computer and use it in GitHub Desktop.
Save netslow/922115 to your computer and use it in GitHub Desktop.
Compare tail recursion, list folding and classic approach
package org.halfcup.scala
import scala.annotation._
object TestTailRec {
def main(args: Array[String]): Unit = {
val list = List("one", "two", "three", "four", "five", "six", "seven", "eight", "nine","ten")
def maxWidth(s: List[String]) = {
var maxLength = 0
for (str <- s) {
maxLength = maxLength.max(str.length)
}
maxLength
}
@tailrec
def maxWidthRec(s: List[String], max: Int): Int = {
s match {
case Nil => max
case _ => maxWidthRec(s.tail, max.max(s.head.length))
}
}
def maxWidthFold(list:List[String]):Int = {
return list.foldLeft("")((s1, s2) =>
if (s1.length > s2.length) s1
else s2).length
}
for (i <- 1 to 100) {
val t3 = System.currentTimeMillis;
for (i <- 1 to 1000000) {
val max = maxWidth(list)
}
val t4 = System.currentTimeMillis - t3
println("Simple: " + t4)
val t1 = System.currentTimeMillis;
for (i <- 1 to 1000000) {
val max = maxWidthRec(list, 0)
}
val t2 = System.currentTimeMillis - t1
println("Tailrec:" + t2)
val t10 = System.currentTimeMillis
for (i <- 1 to 1000000) {
val max = maxWidthFold(list)
}
val t20 = System.currentTimeMillis - t10
println("Fold: " + t20)
}
}
}
@netslow
Copy link
Author

netslow commented Apr 15, 2011

Sample output:
Simple: 221
Tailrec:182
Fold: 81

@netslow
Copy link
Author

netslow commented Apr 15, 2011

On the other hand I get quite reasonable result when I run it from terminal:
Simple: 46
Tailrec:53
Fold: 47

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