时间戳

首页 > 解决方案 > 函数式编程：很难理解这个函数是如何惰性求值的

scala - 函数式编程：很难理解这个函数是如何惰性求值的

问题描述

我正在阅读这Functional Programming in Scala本书，并且在关于惰性评估的部分。有一个练习可以takeWhile使用foldRight. 我能够成功完成它，但是当我添加打印语句时，我看到它似乎正在处理我没想到的。我对此感到非常困惑。

这是代码：

trait McStream[+A] {
    def uncons: Option[(A, McStream[A])]

    def isEmpty: Boolean = uncons.isEmpty

    def toList: List[A] = {
      uncons match {
        case Some(head -> tail) => head :: tail.toList
        case None => Nil
      }
    }

    def foldRight[B](z: => B)(f: (A, => B) => B): B = {
      uncons match {
        case Some(head -> tail) =>
          println(s"Inside foldRight, head is $head")
          f(head, tail.foldRight(z)(f))
        case None => z
      }
    }

    // TODO how does evaluate?  Trace steps
    // TODO it seems to be storing a deferred takeWhile in the `b` variable that evaluates during the cons
    def takeWhile(p: A => Boolean): McStream[A] = {
      foldRight(McStream.empty[A]) { (a, b) =>
        println(s"a is $a, b is $b")
        if (p(a)) {
          McStream.cons(a, b)
        } else {
          McStream.empty
        }
      }
    }
}

使用构造函数的辅助对象：

object McStream {
    def empty[A]: McStream[A] = new McStream[A] {
      override def uncons: Option[(A, McStream[A])] = None
    }

    def cons[A](hd: => A, tl: => McStream[A]): McStream[A] = {
      new McStream[A] {
        lazy val uncons = Some((hd, tl))
      }
    }

    def apply[A](as: A*): McStream[A] = {
      if (as.isEmpty) empty
      else cons(as.head, apply(as.tail: _*))
    }
  }
}

这是我正在运行的测试：

"take while a predicate is matched" in {
      val stream = McStream(1, 2)
      stream.takeWhile(_ < 2).toList shouldEqual List(1)
    }

这是我得到的输出：

Inside foldRight, head is 1
Inside foldRight, head is 2
a is 2, b is McStream(None)
a is 1, b is McStream(None)
Inside foldRight, head is 2
a is 2, b is McStream(None)

我对最后两行感到困惑，对我来说，它似乎应该一直递归到列表的末尾，然后如果谓词匹配，则将当前处理的尾部连接到下一个元素，或者将其替换为McStream否则为空。那时，它应该只是返回列表，而不是进行附加foldRight和评估。

据我所知，这是评估顺序：

Stream(1, Stream(2, Stream.empty)).takeWhile(_ < 2)
should print Inside foldRight, head is 1
Stream(2, Stream.empty).takeWhile(_ < 2)
should print Inside foldRight, head is 2
Stream.empty.takeWhile(_ < 2)
End of recursion, starts to return
Stream(2, Stream.empty).takeWhile(_ < 2)
should print a is 2, b is Stream.empty
Stream(1, Stream.empty).takeWhile(_ < 2)
should print a is 1, b is Stream.empty
1 #:: Stream.empty

提前致谢！

标签： scalafunctional-programming

解决方案

事实证明，我用来尝试理解评估（println语句）的机制正在强制评估并导致上述问题。当我删除它应该评估的打印语句时。

不要println在你的懒惰评估中使用！

推荐阅读