Ayutaya.com

簡潔すぎﾜﾛﾀｗ

import Stream._
def sieve[A <% BigInt](xxs: Stream[A]): Stream[A] = xxs match {
  case p #:: xs => cons(p, sieve(xs.filter(_ % p != 0)))
}
lazy val primes = sieve(from(2))

先頭 10 個。

scala> primes.take(10).toList
res0: List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)

Fri Apr 22 2011: ついでに、遅延評価版のクイックソートも。まずは、普通に eager 評価のリストで書いた場合:

def qsort[A <% Ordered[A]](xxs: List[A]): List[A] = xxs match {
  case Nil => Nil
  case p :: xs =>
    qsort(xs filter(_ <= p)) ++ (p :: qsort(xs filter(p < _)))
}

ストリームで書くと、以下のように:

import Stream._
def qsort[A <% Ordered[A]](xxs: Stream[A]): Stream[A] = xxs match {
  case Empty => Empty
  case p #:: xs =>
    qsort(xs filter(_ < p)) ++ (p #:: qsort(xs filter(p <= _)))
}

ほぼ同じですが、”Empty” や “#::” などが特徴的です。不用意に無限長ストリームのソートなんかしちゃダメですよ。filter() が返ってきません。