2

我正在关注这本书Functional programming in Scala，特别是您实现简单 Stream 特征和伴随对象的部分。作为参考，这是我们迄今为止在伴生对象中的内容

object Stream {
  def empty[A]: Stream[A] =
    new Stream[A] {
      def uncons = None
    }

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

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

到目前为止的特征：

trait Stream[A] {
  import Stream._

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

  def toList: List[A] = uncons match {
    case None => Nil: List[A]
    case Some((a, as)) => a :: as.toList
  }

  def #::(a: => A) = cons(a, this)

  def take(n: Int): Stream[A] =
    if (n <= 0)
      empty
    else (
      uncons
      map { case (a, as) => a #:: (as take (n - 1)) }
      getOrElse empty
    )
}

下一个练习需要我编写一个实现takeWhile，我认为下面会做

  def takeWhile(f: A => Boolean): Stream[A] = (
    uncons
    map { case (a, as) => if (f(a)) (a #:: (as takeWhile f)) else empty }
    getOrElse empty
  )

不幸的是，似乎我得到了一个我无法追踪的方差错误：

error: type mismatch;  found   : Stream[_2] where type _2 <: A 
required: Stream[A]
Note: _2 <: A, but trait Stream is invariant in type A.
You may wish to define A as +A instead. (SLS 4.5)
           getOrElse empty
           ^

我可以添加方差注释，但在此之前，我想了解这里出了什么问题。有什么建议么？

4

2 回答 2

2

这似乎是类型推断的问题，因为如果您明确指定 subexpression 的类型，它就会起作用uncons map { case (a, as) => if (f(a)) (a #:: (as takeWhile f)) else empty }。

def takeWhile(f: A => Boolean): Stream[A] = {
  val mapped:Option[Stream[A]] = uncons map {
    case (a, as) => if (f(a)) (a #:: (as takeWhile f)) else empty
  }
  mapped getOrElse empty
}
于 2012-08-16T09:30:30.550 回答
1

要完成其他答案，请empty在此行：

map { case (a, as) => if (f(a)) (a #:: (as takeWhile f)) else empty }

推断为empty[Nothing]，这意味着(a #:: (as takeWhile f)) else empty推断为Stream[Foo <: A]并且由于 aStream[A]是预期的并且Stream是不变的，因此您有一个错误。

所以这给了我们最干净的方法来解决这个问题：只需注释empty：

map { case (a, as) => if (f(a)) (a #:: (as takeWhile f)) else empty[A] }

然后它编译得很好。

这不会发生在原始Stream版本中，因为它是协变的，所以要么你真的想Stream.empty成为 a Stream[Nothing]（就像Nil是 a一样List[Nothing]），要么你不在乎。

现在，究竟为什么它被推断为empty[Nothing]而不是empty[A]，这可能隐藏在 SLS 6.26.4“本地类型推断”中的某个地方，但这部分不能真正被指责为易于阅读......

作为一个经验法则，每当你调用方法时总是要保持怀疑：

  • 具有类型参数，其唯一推断方法是预期的返回类型（通常是因为它们没有参数），
  • 并且同时预期的返回类型本身应该是从其他地方推断出来的。
于 2012-08-22T18:11:57.357 回答