我正在看“Scala 中的 FP”一书中的练习 5.8,问题是:
“将它们稍微推广到函数常量,它返回给定值的无限流。”
def constant[A](a: A): Stream[A]
我的解决办法是:
def constant[A](a: A): Stream[A] =
Stream.cons(a, constant(a))
当我提到标准解决方案时,它是:
// This is more efficient than `cons(a, constant(a))` since it's just
// one object referencing itself.
def constant[A](a: A): Stream[A] = {
lazy val tail: Stream[A] = Cons(() => a, () => tail)
tail
}
上面写着“更高效”,见 here .
我能知道为什么它更有效吗? AFAIK,Streams 中的 cons 构造函数已经将头部和尾部标记为惰性:
def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
lazy val head = hd
lazy val tail = tl
Cons(() => head, () => tail)
}
为什么我们还需要再次将尾部标记为懒惰?我不太明白这里的重点。
最佳答案
这更像是对@ElBaulP 答案的评论,而不是对其自身权利的回答,但评论太大了。
我认为您错过了优化的根源,即使它在上面的评论中明确说明。事实证明val tail
在 constant
是 lazy
是实现细节,或者更确切地说是使优化的主要来源成为可能的技巧。而优化的主要来源是tail
是自指的。
让我们暂时摆脱所有 lazy
东西。假设 Cons
被定义为
case class Cons[+A](h: A, t: () => Stream[A]) extends Stream[A]
让我们定义
constant
作为def constant[A](a: A): Stream[A] = {
val tailFunc: () => Stream[A] = () => tail
val tail: Stream[A] = Cons(a, tailFunc)
tail
}
是的,这是一个语法上无效的程序,因为
tailFunc
用途 tail
仅在下一行定义。但是想象一下 Scala 可以编译它。我认为现在很清楚 constant
这样的实现只会创建一个类 Cons
的实例每次调用,无论您尝试迭代返回的流多长时间,都会使用该实例。什么定义
tail
如 lazy
允许只是使代码在逻辑上等同于上述编译而没有错误。从实现的角度来看,它类似于以下内容:class Lazy[A](var value:A)
def constant[A](a: A): Stream[A] = {
val lazyTail: Lazy[Stream[A]] = new Lazy(null)
// this tailFunc works because lazyTail is already fixed and can be safely
// captured although lazyTail.value will be changed
val tailFunc: () => Stream[A] = () => lazyTail.value
lazyTail.value = new Stream(a, tailFunc)
lazyTail.value
}
此代码与实际
lazy
不完全匹配在许多细节中实现,因为它实际上很热切,但我认为这表明您并不真正需要 lazy
使优化工作(但以使用 var
为代价,Scala 编译器在其真实的、更复杂的 lazy
实现中无论如何都会这样做)。在你天真的实现中
def constant[A](a: A): Stream[A] = Stream.cons(a, constant(a))
tail
的惰性求值允许您不会因为 constant
的递归调用而立即因堆栈溢出而失败从本身。但是当你这样做时constant(whatever).tail
, tail
正在评估所以 constant
方法再次被调用,一个新的 Cons
对象被创建。每次都会发生这种情况tail
被称为新 head
.再次重申,
lazy val tail
只是一个技巧,允许 tail
在创建时引用自身,真正重要的部分是 tail
引用本身允许只使用一个对象进行迭代,而不是每个下一个对象一个对象.tail
称呼。
关于scala - 为什么constant() 解决方案比 "FP in Scala"5.8 中更简单的解决方案更有效?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54045115/