练习：在Scala中实现Stream

我正在关注Functional programming in Scala这本书，特别是您实现简单的Stream特征和伴侣对象的部分。作为参考，这里是我们至今在同伴obejct练习：在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 
     ^

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

来源

2012-08-16 Andrea

这似乎是类型推断的问题，因为如果您明确指定子表达式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-16 09:30:30

谢谢，这个作品。你有什么线索为什么类型推理在这种情况下失败？在Scala中常见的是必须输入中间值（当然，除非像'Nil：List [Int]'）这样的不明确的情况除外） – Andrea 2012-08-16 10:18:25

我不知道它为什么会失败，但并不常见。尽管有一些已知的限制，例如递归函数或多个返回值。也许你应该在邮件列表中询问这个问题。 – 2012-08-16 10:25:20

要完成了一下对方的回答中，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]和因为Stream[A]预期和Stream是不变，你有一个错误。

所以这给了我们解决这个问题最彻底的方法：只标注empty：

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

然后它编译罚款。

这并不与原Stream发生，因为它是协变的，所以无论是你真正想要Stream.empty成为Stream[Nothing]（就像Nil是List[Nothing]），或者你不在乎。

现在，至于为什么它被推断为empty[Nothing]而不是empty[A]，这可能隐藏在SLS 6.26.4“Local Type Inference”的某处，但这部分不能被指责为易于阅读......

按规定拇指，总是可疑的，只要你调用方法：

具有类型参数的唯一方式推断是预期收益类型（通常是因为他们没有参数），
并在同一时间的预期回报类型是它我应该从其他地方推断自己。

来源

2012-08-22 18:11:57 gourlaysama

练习：在Scala中实现Stream

回答

相关问题