Lazy val在Scala中实现惰性列表

Question

我正在尝试通过实现我自己的懒惰列表版本来学习如何在Scala中使用内置的懒惰:

object LazyList {

  def empty[A] : LazyList[A] = new LazyList[A] {
    lazy val uncons = None
  }

  def cons[A](h : => A, t : => LazyList[A]) : LazyList[A] = new LazyList[A] {
    lazy val uncons = Some( (h,t) )
  }

  def from(s : Int) : LazyList[Int] = new LazyList[Int] {
    lazy val uncons = Some( (s,from(s + 1)) )
  }
}

trait LazyList[A] {

  import LazyList._

  def uncons : Option[(A,LazyList[A])]

  def fmap[B](f : A => B) : LazyList[B] = uncons match {
    case None          => empty
    case Some( (h,t) ) => cons(f(h),t.fmap(f))
  }

  def take(i : Int) : LazyList[A] = uncons match {
    case None          => empty
    case Some( (h,t) ) => if (i <= 0) empty else cons(h,t.take(i - 1))
  }

  override def toString : String = uncons match {
    case None          => "[]"
    case Some( (h,t) ) => "[" ++ h.toString ++ ",..]"
  }
}

这似乎有效,我可以,例如,映射{ _ + 2}到无限列表:

> LazyList from 1 fmap { _ + 2 }
res1: LazyList[Int] = [2,..]

我决定实现,我通常喜欢使用一些功能drop,take等等,我已经能够实现它们除了inits.我的实施inits是:

  def inits : LazyList[LazyList[A]] = uncons match {
    case None          => empty
    case Some( (h,t) ) => cons(empty,t.inits.fmap(cons(h,_)))
  }

问题是由于某种原因它无法在无限列表上工作.例如,我不能写:

  > LazyList from 1 inits

因为它永远运行 问题似乎是fmap在t.inits那之后,由于某种原因,打破了懒惰(如果我删除fmap它是错误的但是懒惰).为什么要fmap强制执行严格性,并且根据我的类型LazyList,如何inits实现它可以在无限列表上工作？

Answer 1

二者fmap并inits在被调用时剥离一个实际(非延迟)元件; 他们俩uncons.由于他们互相称呼,因此链条永远不会终止LazyList.

具体来说,请注意uncons返回不是=> LazyList实际的LazyList,所以当你打电话时

Some( (h,t) )

该评估 t.如果对a的t调用进行评估uncons,那么它也将进行评估并且您将进入堆栈溢出竞争.这里注意到这一点很棘手,因为它是双递归.

你需要让其中一个剥离零拷贝.你可以做到这一点的一种方法是通过使uncons元组的第二个参数变为惰性(显式地,通过使它变为一个Function0):

object LazyList {
  def empty[A]: LazyList[A] = new LazyList[A] {
    lazy val uncons = None
  }

  def cons[A](h: => A, t: => LazyList[A]) : LazyList[A] = new LazyList[A] {
    lazy val uncons = Some( (h,() => t) )
  }

  def from(s: Int): LazyList[Int] = new LazyList[Int] {
    lazy val uncons = Some( (s,() => from(s + 1)) )
  }
}

trait LazyList[A] {
  import LazyList._

  def uncons: Option[(A,() => LazyList[A])]

  def fmap[B](f: A => B): LazyList[B] = uncons match {
    case None          => empty
    case Some( (h,t) ) => cons(f(h),t().fmap(f))
  }

  def take(i: Int): LazyList[A] = uncons match {
    case None          => empty
    case Some( (h,t) ) => if (i <= 0) empty else cons(h,t().take(i - 1))
  }

  override def toString: String = uncons match {
    case None          => "[]"
    case Some( (h,t) ) => "[" ++ h.toString ++ ",..]"
  }
}

然后你的实现工作:

  def inits: LazyList[LazyList[A]] = uncons match {
    case None          => empty
    case Some( (h,t) ) => cons(empty,t().inits.fmap(cons(h,_)))
  }

拥有这样做的内部解构器以及适合尾巴的外向解构器可能更好.