code

2016年11月11日 星期五

Scala筆記 26 - 無限長度的Streams!

無限制長度的Stream

有了lazy evaluation這個工具,我們可以寫出無限長度的數列Stream,我是把它看成一種,例如自然數Stream:

def nats(from:Int) :Stream[Int] = Stream.cons(from, nats(from+1))

nats(1).take(10).toList //res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)

上面的expression只有當toList被evaluate時,才會去evalute nats的每個item。所以take(10)會開始evaluate nats(1)這個Stream的前十個item:

Streams.cons(1, nats(2))   //1st item is 1
Steams.cons(2, nats(3))   //2nd item is 2
.
.
Streams.cons(10, nats(11)) //10th item is 10
停止evaluation

有了這個自然數列,我們可以根據某個演算法來計算出一個Prime Stream。此古老演算法檢視所有的自然數,每遇到一個新的自然數,就把它的倍數從自然數列中去除掉,非常天真的演算法,但是符合Streams特性:

def sievePrimes(nats:Stream[Int]) : Stream[Int] = {
  nats.head #:: sievePrimes( nats filter(x => x% nats.head != 0 ))
}

sievePrimes(nats(2)).take(10).toList //res1: List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)



沒有留言:

張貼留言