error: constructor cannot be instantiated to expected type

Question

I'm new to Scala and I'm reading the Functional Programming in Scala book, on one of their exercises I got two compilation errors which I don't understand why I'm getting those. I'm getting the following two errors on the code below:

error: value toList is not a member of Chapter5.Stream[Int]
    val list : List[Int] = st.toList
                              ^
Stream.scala:22: error: constructor cannot be instantiated to expected type;
 found   : Chapter5.Cons[A]
 required: Chapter5.Stream.type
    case Cons(h,t) => h() :: t().toList
         ^
two errors found

This is the trait and the companion object:

package Chapter5

sealed trait Stream[+A]

case object Empty extends Stream[Nothing]
case class Cons[+A](h : () => A, t : () => Stream[A]) extends Stream[A]

object Stream{
  def cons[A](hd : => A, tl: => Stream[A]): Stream[A] = {
    lazy val head = hd
    lazy val tail = tl
    Cons(() => head, () => tail)
  }

  def empty[A]: Stream[A] = Empty

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

  def toList[A]: List[A] = this match{
    case Cons(h,t) => h() :: t().toList
    case _ => List()
  }

}

When I try to call toList the following way I also get an error:

package Chapter5

object Main {
  def main(args : Array[String]) = {
    val arr = Array(1,3,4,6)
    val st : Stream[Int] = Stream.apply(arr : _*)
    val list : List[Int] = st.toList
  }
}

I don't understand these errors at all, for the first case: Obviously I define a toList method on the object. For the second Cons extends the Stream trait, so I don't understand why I cannot use pattern matching like this.

You're defining the methods inside the companion object and matching toList on this, which is Stream.type of the companion. That's probably not what you want. — Yuval Itzchakov

HTNW HTNW · Accepted Answer · 2017-01-02T19:33:28

You are defining these methods in object Stream, not the trait Stream. The companion object of a type is (almost) completely unrelated to the type itself. The only things that relate a companion object with its type are:

They happen to have the same name. (Technically, the names are in different namespaces (type vs. term), so this is just superficial.)
They can see each other's private parts. (This may be made stricter by declaring things private[this].)

Therefore, this on line 21 does not mean "the Stream on which we are operating", it means "this singleton object, called Stream, which is almost unrelated to the trait, also called Stream." Similarly, on line 22, Stream doesn't have a toList method; it's Stream.type (the type of the companion) that does.

Either modify toList to take a stream parameter:

object Stream
  def toList[E](stream: Stream[E]): List[E] = stream match {
    //         !^^^^^^^^^^^^^^^^^!            ^!!!!^
  }
}

or move toList (and probably cons) into trait Stream:

sealed trait Stream[+E] {
  def cons(hd: => E) = ???
  def toList: List[E] = ???
}

error: constructor cannot be instantiated to expected type

1 Answers