为什么constant()解决方案比"FP in Scala"5.8中更容易的解决方案更有效？

Question

我正在阅读"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
}

其中说"效率更高",请看这里.

我能知道它为什么效率更高？Streams中的cons构造函数AFAIK已经将头部和尾部标记为懒惰:

def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = { 
  lazy val head = hd 
  lazy val tail = tl 
  Cons(() => head, () => tail) 
}

为什么我们仍然需要将尾巴标记为懒惰？我不太明白这一点.

Answer 1

这更像是对@ElBaulP答案的评论,而不是对自己权利的回答,但对于评论来说它太大了.

我认为你错过了优化的根源,即使它已在上面的评论中明确说明.事实上,在val tail中constantIS 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为lazyallow的只是使代码在逻辑上等同于上面的编译而没有错误.从实现的角度来看,它类似于:

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调用一个对象的事实.