Scalaの無限リスト(Stream)でいろいろと

Main.scala

// 初期値とstepを指定して永遠にカウントするItrator
class Counter[T:Numeric](init:T = 0,step:T = 1) extends Iterator[T] {
  var cnt = init
  def hasNext = true
  def next = {
    cnt = implicitly[Numeric[T]].plus(cnt, step)
    cnt
  }
  // 自分をStreamにする
  def asStream = Stream.continually( next )
}

object Main extends Application {

  // via inforno :: Scalaで無限リスト：Haskellライクに : http://inforno.net/articles/2008/02/09/scala-infinite-list-like-a-haskell
  def repeat[T](a:T) = Stream.const(a)
  def cycle[T](a:Iterable[T]) = Stream.const(a).flatMap(v=>v)
  def iterate[T](x:T)(f:T => T):Stream[T] = x #:: iterate(f(x))(f)
  def replicate[T](n:Int, elem:T) = Stream.make(n, elem)

  println("-" * 80)
  println("Counter")
  val counter = new Counter(100, 1)
  counter.asStream.filter{ _ % 3 == 0 }.filter{ _ % 5 == 0 }.takeWhile{ 200 > }.print

  println()
  println("-" * 80)

  // カウンターはこっちのがエレガントかも
  // 自然数のStream[Int]
  val numbers = (init:Int) => iterate(init){1 + }

  // 三角数
  println("-" * 80)
  println("三角数:")
  val triangle:Stream[Int] = 1 #:: numbers(2).scanLeft(1){(a,b) => a + b }
  triangle take 10 print

  println()
  println("-" * 80)

  // 階乗
  println("-" * 80)
  println("階乗:")
  val factorial = 1 #:: numbers(2).scanLeft(1){(a, b) => a * b }
  factorial take 10 print

  println()
  println("-" * 80)

  // フィボナッチ その1
  println("-" * 80)
  println("フィボナッチその1:")
  val fib1:Stream[Int] = 0 #:: 1 #:: fib1.zip(fib1 tail).map{ case (a,b) => a + b }
  fib1 take 20 print

  println()
  println("-" * 80)

  // フィボナッチ その2
  println("-" * 80)
  println("フィボナッチその2:")
  val fib2:Stream[Int] = 0 #:: fib2.scanLeft(1){(a, b) => a + b }
  fib2 take 20 print

  println()
  println("-" * 80)

  // 素数 from http://haskell.org/haskellwiki/Prime_numbers

  // エラストテネスの篩
  //  haskell : sieve (x:xs) = x : sieve [y | y <- xs,   y `mod` x /= 0]
  println("-" * 80)
  println("エラストテネスの篩")
  def sieve(stream:Stream[Int]):Stream[Int] = {
    val x #:: xs =  stream
    x #:: sieve( for( y <- xs if y % x != 0) yield{ y })
  }
  sieve(numbers(2)) take 10 print

  println()
  println("-" * 80)

  // primes = 2: 3: filter isPrime [5,7..]
  //    where
  //     isPrime n   = all (notDivs n)
  //                     $ takeWhile (\p-> p*p <= n) (tail primes)
  //     notDivs n p = n `mod` p /= 0
  println("-" * 80)
  println("素数:")
  lazy val primes:Stream[Int] = {
    def notDivs(n:Int, p:Int) = n % p != 0
    def isPrime(n:Int):Boolean = primes.takeWhile{ p => p * p <= n }.view.forall{ p => notDivs(n,p)}
    2 #:: 3 #:: (5 #:: numbers(7)).filter{ p => isPrime(p) }
  }
  primes take 10 print

  println()
  println("-" * 80)
}