title: Exercise: implementing Stream in Scala
body: <p>I am following the book <code>Functional programming in Scala</code> and in particular the section where you implement a simple Stream trait and companion object. For reference, here is what we have so far in the companion obejct</p>
  
  <pre><code>object Stream {
    def empty[A]: Stream[A] =
      new Stream[A] {
        def uncons = None
      }
  
    def cons[A](hd: =&gt; A, tl: =&gt; 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: _*))
  }
  </code></pre>
  
  <p>and the trait so far:</p>
  
  <pre><code>trait Stream[A] {
    import Stream._
  
    def uncons: Option[(A, Stream[A])]
  
    def toList: List[A] = uncons match {
      case None =&gt; Nil: List[A]
      case Some((a, as)) =&gt; a :: as.toList
    }
  
    def #::(a: =&gt; A) = cons(a, this)
  
    def take(n: Int): Stream[A] =
      if (n &lt;= 0)
        empty
      else (
        uncons
        map { case (a, as) =&gt; a #:: (as take (n - 1)) }
        getOrElse empty
      )
  }
  </code></pre>
  
  <p>The next exercise requires me to write an implementation for <code>takeWhile</code> and I thought the following would do</p>
  
  <pre><code>  def takeWhile(f: A =&gt; Boolean): Stream[A] = (
      uncons
      map { case (a, as) =&gt; if (f(a)) (a #:: (as takeWhile f)) else empty }
      getOrElse empty
    )
  </code></pre>
  
  <p>Unfortunately, is seems that I get a variance error that I am not able to track down:</p>
  
  <pre><code>error: type mismatch;  found   : Stream[_2] where type _2 &lt;: A 
  required: Stream[A]
  Note: _2 &lt;: A, but trait Stream is invariant in type A.
  You may wish to define A as +A instead. (SLS 4.5)
             getOrElse empty
             ^
  </code></pre>
  
  <p>I could add a variance annotation, but before doing that I would like to understand what is going wrong here. Any suggestions?</p>