Reinvention of the Wheel Series, "Bubble Sort in Scalaz".

bubbleSort.scala

import scalaz._
import Scalaz._

object Bubble {
  def bubbleSort[A: Order](xs: List[A]) = xs.unfold[Stream, A] {
    _.foldr[Option[(A, List[A])]](none){ (x, zs) =>
      zs.fold({case (y, ys) => (x lt y).fold((x, y::ys), (y, x::ys))}, (x, nil[A])).some
    }
  }
}

result.txt

// 泡が浮く種類のバブルソート
// 遅延評価で必要な数だけ浮いてくるので、先頭数個取るだけなら高速

scala> val s = Bubble.bubbleSort((100000 to 1 by -1).toList)
s: Stream[Int] = Stream(1, ?)

scala> s take 10 print
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, empty