Scalaでクイックソート

Scalaで3通りのクイックソートを実装してみました。

object QuickSort extends App {

  val nums = List(32, 23, 10, 1, -100, 3, 999)

  {
    // 9行: ふつうの実装
    def quickSort(nums: List[Int]): List[Int] = {
      if (nums.isEmpty)
        List()
      else {
        val left = nums.filter(_ < nums.head)
        val right = nums.filter(nums.head < _)
        quickSort(left) ++ List(nums.head) ++ quickSort(right)
      }
    }

    println(quickSort(nums))
  }

  {
    // 7行: matchを使った実装
    def quickSort(nums: List[Int]): List[Int] = nums match {
      case List() => List()
      case head :: tail =>
        val left = tail.filter(_ < head)
        val right = tail.filter(head < _)
        quickSort(left) ++ List(head) ++ quickSort(right)
    }

    println(quickSort(nums))
  }

  {
    // 7行: foldを使った実装
    def quickSort(nums: List[Int]): List[Int] = {
      nums.headOption.fold(List[Int]()){ head =>
        val left = nums.filter(_ < head)
        val right = nums.filter(head < _)
        quickSort(left) ++ List(head) ++ quickSort(right)
      }
    }

    println(quickSort(nums))
  }
}

ifやmatchを使った実装は、比較的わかりやすいと思います。
foldを使った実装は、関数型っぽい実装だと思います。