Strictness 和 Laziness (1)

想像一下你想要使用 List 來做一系列的資料操作，

scala> List(1, 2, 3, 4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)
List(36, 42)

此操作會在每一個轉換中建立暫時用的 List，當做下一個轉換的輸入使用，然後在立即捨棄，直到結束，

List(1, 2, 3, 4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)
List(11, 12, 13, 44).filter(_ % 2 == 0).map(_ * 3)
List(12, 14).map(_ * 3)
List(36, 42)

難道 functional programming 中沒有比較有效率的處理方式嗎？將所有轉換一次處理，避免建立暫時用的 List，

也許我們可以選擇用 while 迴圈來處理，但這樣就得捨棄上面程式那種優美、可組合式的流式處理，寫 functional programming 的人更喜歡用 high-order function 加上多種 function 組合來取代迴圈；

好家在是有的，我們可以使用 non-strictness (laziness) 來融合所有迴圈轉換。

strict 和 non-strict function

在示範 lazy List 之前，我們先來了解 strict 和 non-strict 的區別，

strict/non-strict 是 function 的一種屬性，若我們稱 function 是 strict，表示該 function 會 evaluate (執行) 所有參數，例如以下程式，當呼叫 square(5.0 + 1.0)，則 square function 會接收到已被 evaluate 的值 6，

def square(x: Double): Double = x * x

大多數的程式語言預設都是 strict，Scala 也是。

而 function 是 non-strict 的話，表示該 function 可以選擇是否要 evaluate (執行) 1 個或多個參數，

例如大多數程式語言都有的 && 和 || ，雖然它們是程式語言的語法之一，倘若把它們當 function 來看的話，它們都是 non-strict，它們會選擇是否要 evaluate 所有參數，例如以下程式使用 &&，當第一個參數 boolean 是 false 時，第二個 boolean 參數不會 evaluate，

scala> false && { println("hi"); true }
false

然後 || 只有當第一個 boolean 參數是 false 時，才會 evaluate 第二個 boolean 參數，

scala> true || { println("hi"); false }
true

而另一個符合 non-strict 屬性的語法是 if 判斷式，如果我們把 if 當成 function 來表達的話，如以下程式。

def if2[A](cond: Boolean, onTrue: => A, onFalse: => A): A =
  if cond then
    onTrue
  else
    onFalse

Scala 的 lazy 關鍵字

我們知道了若是 non-strict，參數只有在被確定需要時才會 evaluate，否則就什麼事都不會發生，那如果是以下狀況呢？

scala> def twice(b: Boolean, i: => Int) =
         if b then
           i + i
         else
           0

scala> val x = twice(true, { println("hi"); 1 + 20 })
hi
hi
val x: Int = 42

我們可以看到出現 2 次 hi 字串，可得知 1 + 20 這個表達式被計算了 2 次，但很明顯的是沒意義的調用，

此時就能使用 Scala 的 lazy 關鍵字，lazy 能讓 val 宣告的變數延遲 evaluate，直到它需要被參照使用時，換句話說就是讓 Scala 快取參數 evaluate 後的結果，不會讓它重複被 evaluate，

所以使用 lazy 改寫後的 twice function，i 就只會被 evaluate 1 次而已。

scala> def twice2(b: Boolean, i: => Int) =
         if b then
           lazy val j = i
           j + j
         else
           0    

scala> val x = twice2(true, { println("hi"); 1 + 20 })
hi
val x: Int = 42

LazyList

LazyList 就是 List laziness 的資料型態，老樣子 LazyList 在 Scala 原生庫中已有定義，但我們還是自行實作 LazyList 來練習，

import LazyList.*

enum LazyList[+A]:
  case Empty
  case Cons(h: () => A, t: () => LazyList[A])

object LazyList:
  def cons[A](hd: => A, tl: => LazyList[A]): LazyList[A] =
    lazy val head = hd
    lazy val tail = tl
    Cons(() => head, () => tail)

  def empty[A]: LazyList[A] = Empty

  def apply[A](as: A*): LazyList[A] =
    if as.isEmpty then empty
    else cons(as.head, apply(as.tail *))

在 enum 的定義上，跟 List 最大的不同是使用 () => A 和 () => LazyList[A] 取代了 List 的 strict 值，

也使用了 cons function 來讓 LazyList 的初始化支持 laziness，最後就是使用 empty function 來 new Empty，讓 apply function 能更一致的做型別推斷；

high-order function 型別 () => A 等同於 [Function0[A]][https://scala-lang.org/api/3.x/scala/Function0.html] 這個 trait，先前我們用過的 high-order function (A, B) => C 等同於 Function2[A, B, C] ，以此類推最多支援到 Function22。

如果我們想走訪所有資料，請務必要留意調用 h() 以取得原始的值，例如我想取得 LazyList 的第一個值，並轉為 Option。

  def headOption: Option[A] = this match
    case Empty => None
    case Cons(h, _) => Some(h())

Exercise D10-1

實作 toList function 讓 LazyList 轉為 List。

 def toList: List[A]

Exercise D10-2

實作 take function，取得 LazyList 的前 n 個元素。

實作 drop function，丟掉 LazyList 的前 n 個元素。

def take(n: Int): LazyList[A] 
def drop(n: Int): LazyList[A]

Exercise D10-3

取得 LazyList 前面所有符合條件的元素，直到某個元素不符合。

def takeWhile(f: A => Boolean): LazyList[A]

明天在來介紹一下 LazyList 的進階用法吧！

Exercise answer

strict 和 non-strict function

Scala 的 lazy 關鍵字

LazyList

tshine73

發佈留言取消回覆