基于 foldRight() 的 filter() 溢出

Question

按照本书 "Functional Programming in Scala" 第 5 章中的示例，我实现了惰性列表并通过尝试在斐波那契数列中查找素数对其进行了测试。 Whosebugs 书中给出的默认实现（我的实现基于此）。但是，如果我将 filter() 函数的实现从基于 foldRight 的实现更改为使用模式匹配的实现，则 Whosebug 问题得到解决。为什么会这样？

1）主要功能： filter_overflow() 是使用 foldRight 和溢出实现的。 filter()使用模式匹配实现，不会溢出

package example

object Hello {
  import datastructures._
  import datastructures.LazyList._
  def main(args: Array[String]): Unit = {
  def fibs: LazyList[BigInt] =
      LazyList[BigInt](0, 1) append unfold[(BigInt, BigInt), BigInt]((0, 1))(_ match { case (a, b) => (a + b, (b, a + b)) })
    println(fibs.filter(_.isProbablePrime(8)).drop(BigInt(21)).headOrElse(-1))
    println(fibs.filter_overflow(_.isProbablePrime(8)).drop(BigInt(21)).headOrElse(-1))
 }
}

2) LazyList 实现：

package datastructures

sealed trait LazyList[+A] {
  import LazyList.{empty, cons, join, unit}
  def toList: List[A] = this.foldRight(List[A]())(_ :: _)
  def head: A = this match {
    case Cons(h, _) => h()
  }
  def headOrElse[B >: A](default: B): B = this match {
    case Empty => default
    case Cons(h, _) => h()
  }
  def tail: LazyList[A] = this match {
    case Cons(h, t) => t()
  }
  def map[B](f: A => B): LazyList[B] =
    this.foldRight(empty[B])((a, bs) => cons(f(a), bs))
  def flatMap[B](f: A => LazyList[B]): LazyList[B] =
    join(this map f)
  def foldRight[B](z: => B)(f: (A, => B) => B): B = this match {
    case Empty => z
    case Cons(h, t) => f(h(), t().foldRight(z)(f))
  }
  def append[B >: A](that: => LazyList[B]): LazyList[B] =
    this.foldRight(that)(cons(_, _))
  @annotation.tailrec
  final def drop(n: BigInt): LazyList[A] =
    if (n <= BigInt(0)) this else this.tail.drop(n - BigInt(1))
  def take(n: BigInt): LazyList[A] =
    if (n <= BigInt(0)) empty[A]
    else cons(this.head, this.tail.take(n - BigInt(1)))
  def filter_overflow(f: A => Boolean): LazyList[A] =
    this.foldRight(empty[A])((x, xs) => if (f(x)) cons(x, xs) else xs)
  def filter(pred: A => Boolean): LazyList[A] = this match {
    case Empty => empty[A]
    case Cons(h, t) =>
      if (pred(h())) cons(h(), t() filter pred)
      else t() filter pred
  }
}
case object Empty extends LazyList[Nothing]
case class Cons[+A](
  hd: () => A,
  tl: () => LazyList[A]) extends LazyList[A]
object LazyList {
  def unit[A](a: A): LazyList[A] = LazyList(a)
  def apply[A](as: A*): LazyList[A] =
    if (as.isEmpty) empty[A]
    else cons(as.head, apply(as.tail: _*))
  def cons[A](h: => A, t: => LazyList[A]): LazyList[A] = {
    // lazy val _h: A = hd
    // lazy val _t: LazyList[A] = tl
    // Cons(() => _h, () => _t)
    Cons(() => h, () => t)
  }
  def empty[A]: LazyList[A] = Empty
  def join[A](ss: => LazyList[LazyList[A]]): LazyList[A] =
    ss.foldRight(empty[A])(_ append _)
  def map2[A, B, C](
    as: LazyList[A],
    bs: LazyList[B])(f: (A, => B) => C): LazyList[C] =
    as flatMap(x => bs flatMap(y => unit(f(x, y))))
  def unfold[S, A](s: S)(f: S => (A, S)): LazyList[A] = {
    val (a0, s0): (A, S) = f(s) 
    cons(a0, unfold(s0)(f))
  }
}

Answer 1

令我印象深刻的是，两者之间的主要区别在于每次递归时在堆栈框架上放置了多少东西。

注意 filter() 如何使用 foldRight 无法完成谓词 lambda（匿名函数），直到到达终点并且堆栈开始展开。

def foldRight[B](z: => B)(f: (A, => B) => B): B = this match {
  case Empty => z
  case Cons(h, t) => f(h(), t().foldRight(z)(f))
}
def filter(f: A => Boolean): LazyList[A] =
  this.foldRight(empty[A])((x, xs) => if (f(x)) cons(x, xs) else xs)

换句话说，foldRight(/*2 parameters*/) 和 f(/*2 parameters*/) 都会在每次迭代时进入堆栈框架。

另一方面，没有 foldRight() 的 filter() 总是在递归之前完成谓词。

def filter(pred: A => Boolean): LazyList[A] = this match {
  case Empty => empty[A]
  case Cons(h, t) =>
    if (pred(h())) cons(h(), t() filter pred)
    else t() filter pred
}

未完成的 cons(/*2 parameters*/) 也与 filter(/*1 parameter*/)、 一起进入堆栈框架，但并非总是如此。

两者之间的差异，乘以数千次迭代，可能可以解释您得到的结果。

基于 foldRight() 的 filter() 溢出

foldRight() based filter() overflows

scala

lazy-evaluation