Scala筆記 24 - Streams

lazy evaluate的Stream

Streams是個有趣的資料結構，動態性的evaluate list的tail，我在之前用過的語言Java, C, C++都未曾遇過，也有可能我鑽研不夠深入，或許現在有了？我知道Java 8有stream，不過不確定跟Scala這個stream相不相同。

Streams跟List幾乎是一樣的使用方式，差只差在constructor中的tail list是call by reference:

val xs = Stream.cons(1, Stream.cons(2, Stream.empty))

有趣的是看REPL的type是

xs: Stream.Cons[Int] = Stream(1, ?)

如果寫一個range function，stream的版本如下：

def streamRange(lo: Int, hi: Int): Stream[Int] =
  if (lo >= hi) Stream.empty  

  else Stream.cons(lo, streamRange(lo + 1, hi))

這跟我們一般會寫的list版本一模一樣:

def listRange(lo: Int, hi: Int): List[Int] =
  if (lo >= hi) Nil  

  else lo :: listRange(lo + 1, hi)

Stream怎麼implement出來的？

stream是implement這個trait:

trait Stream[+A] extends Seq[A] {
  def isEmpty: Boolean
  def head: A
  def tail: Stream[A]
  ...
}

跟list一樣，只要定義了以上三個methods，其他的所有methods都能建築其上。

它的singleton companion object:

object Stream {
  def cons[T](hd: T, tl: => Stream[T]) = new Stream[T] {
    def isEmpty = false    
    def head = hd
    def tail = tl
  }
  val empty = new Stream[Nothing] {
    def isEmpty = true    
    def head = throw new NoSuchElementException(”empty.head”)
    def tail = throw new NoSuchElementException(”empty.tail”)
  }
}

可以看到cons中的tl參數是call by reference，所以只有在tail method被呼叫到的時候才會evaulate。

所以如果我們執行以下的function:

def streamRange(lo: Int, hi: Int): Stream[Int] = {
  print(lo+” ”)
  if (lo >= hi) Stream.empty  
  else Stream.cons(lo, streamRange(lo + 1, hi))
}

streamRange(1, 10).take(3).toList

實際上會印出123，因為toList會真正要evaluate整個Stream，並且轉換成list。