scala - 为什么constant()解决方案比 “FP in Scala” 5.8中更简单的解决方案更有效？

我正在看《 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/