堆棧安全展開

Question

我想寫一個展開的流。

無法編譯，因爲它不是尾遞歸。

@annotation.tailrec 
def unfold[A, B](a: A)(f: A => Option[(A, B)]): Stream[B] = 
    f(a).map { case (a, b) => b #:: unfold(a)(f) }.getOrElse(Stream.empty) 

......不是真的有效。 （不偷懶）

def unfold[A, B](a: A)(f: A => Option[(A, B)]): Stream[B] = { 
    @annotation.tailrec 
    def go(state: A, next: Stream[B]): Stream[B] = { 
    f(state) match { 
     case Some((a, b)) => go(a, b #:: next) 
     case None => Stream.empty 
    } 
    } 
    go(a, Stream.empty) 
} 
// unfold: [A, B](a: A)(f: A => Option[(A, B)])Stream[B] 
unfold(0)(i => Some((i+1, i))).take(10).toList 
// java.lang.OutOfMemoryError: GC overhead limit exceeded 
// at .$anonfun$res3$1(<console>:18) 
// at .$anonfun$res3$1$adapted(<console>:18) 
// at $$Lambda$1543/299219071.apply(Unknown Source) 
// at .go$1(<console>:19) 
// at .unfold(<console>:24) 
// ... 27 elided 

有點醜，通過Iterator。

def unfold[A, B](a: A)(f: A => Option[(A, B)]): Stream[B] = { 
    new Iterator[B] { 
    private var state: Option[A] = Some(a) 
    private var nextResult: Option[B] = None 

    def next: B = 
     nextResult.getOrElse(
     throw new NoSuchElementException("next on empty iterator")) 

    def hasNext: Boolean = { 
     if (nextResult.isDefined) { 
     true 
     } else { 
     state match { 
      case Some(s) => 
      f(s) match { 
       case Some((nextState, produced)) => 
       nextResult = Some(produced) 
       state = Some(nextState) 
       true 
       case None => false 
      } 
      case None => false 
     } 
     } 
    } 
    }.toStream 
} 

Answer 1

def unfold[A, B](a: A)(f: A => Option[(A, B)]): Stream[B] = 
    f(a).map { case (a, b) => b #:: unfold(a)(f) }.getOrElse(Stream.empty) 

這是正確的，懶惰的（雖然有些REPLs可能會嘗試打印所有流）。

斯卡拉流有懶惰地評估他們的tail。我不認爲你可以通過尾遞歸的方式以一種懶惰的方式影響流的尾部。然而，這是毫無意義的，因爲懶惰給你一疊安全：

assert(unfold(0) { _ => Some((0, 0)) } .toString == "Stream(0, ?)") 

---

assert { 
    try { 
     unfold(0) { _ => Some((0, 0)) }.take(1000000).toList 
     true 
    } catch { 
     case _: StackOverflowError => false 
    } 
    }