Scala by Example

newton-sqrt.scala

   def sqrt(x: Double): Double = sqrtIter(1.0, x)

   def sqrtIter(guess: Double, x: Double): Double =
       if (isGoodEnough(guess, x)) guess
       else sqrtIter(improve(guess, x), x)

   def improve(guess: Double, x: Double) =
       (guess + x / guess) / 2
   def isGoodEnough(guess: Double, x: Double) =
       abs(square(guess) - x) < 0.001

qsort-functional.scala

object QuickSort extends App {
    def sort(xs: Array[Int]): Array[Int] = {
        if (xs.length <= 1) xs
        else {
            val pivot = xs(xs.length / 2)
            Array.concat(
                sort(xs filter (pivot >)),
                     xs filter (pivot ==),
                sort(xs filter (pivot <)))
        }
    }
    println(sort (Array[Int](5,4,3,2,1)).deep.mkString(" "))
}

qsort-imperative.scala

object QuickSort extends App {
    def sort(xs: Array[Int]):Array[Int] = {
        def swap(i: Int, j: Int) {
            val t = xs(i); xs(i) = xs(j); xs(j) = t
        }
        def sort1(l: Int, r: Int) {
            val pivot = xs((l + r) / 2)
            var i = l; var j = r
            while (i <= j) {
                while (xs(i) < pivot) i += 1
                while (xs(j) > pivot) j -= 1
                if (i <= j) {
                    swap(i, j)
                    i += 1
                    j -= 1
                }
            }
            if (l < j) sort1(l, j)
            if (j < r) sort1(i, r)
        }
        sort1(0, xs.length - 1)
        return xs
    }
    println(sort (Array[Int](5,4,3,2,1)).deep.mkString(" "))
}

quicksort.scala:
$ scalac qsort.scala
$ scala QuickSort
1 2 3 4 5
$