CODEWITHSUNDEEP
scalafunctional-programming
Andrea
Andrea

Reputation: 20493

Exercise: implementing Stream in Scala

I am following the book Functional programming in Scala 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

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: _*))
}

and the trait so far:

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
    )
}

The next exercise requires me to write an implementation for takeWhile and I thought the following would do

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

Unfortunately, is seems that I get a variance error that I am not able to track down:

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
           ^

I could add a variance annotation, but before doing that I would like to understand what is going wrong here. Any suggestions?

Upvotes: 2

Views: 1491

Answers (2)

gourlaysama
gourlaysama

Reputation: 11280

To complete a bit the other answer, the empty on this line:

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

is inferred as empty[Nothing], which means that (a #:: (as takeWhile f)) else empty is inferred as Stream[Foo <: A] and since a Stream[A] is expected and Stream is invariant, you have an error.

So this gives us the cleanest way to fix this: just annotate empty:

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

And then it compiles fine.

This does not happen with the original Stream because it is covariant, so either you actually want Stream.empty to be a Stream[Nothing] (just like Nil is a List[Nothing]), or you don't care.

Now, as to exactly why it is inferred as empty[Nothing] and not empty[A], this is probably hidden somewhere in SLS 6.26.4 "Local Type Inference", but this part cannot really be accused of being easy to read...

As a rule a thumb, always be suspicious whenever you call methods:

  • that have type parameters whose only way to infer is the expected return type (usually because they have no arguments),
  • AND at the same time the expected return type is itself supposed to be inferred from somewhere else.

Upvotes: 1

Kim Stebel
Kim Stebel

Reputation: 42047

this seems to be an issue with type inference, because it works if you explicitly specify the type of the 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
}

Upvotes: 2

Related Questions