How this stream's type is casted?

Question

I'm wondering how the type of the Stream below is casted?

type NTy = BigInt
def streamFib(n: Int): NTy = {
  lazy val fibs: Stream[NTy] = 1 #:: 1 #:: fibs.zip(fibs.tail).map(n => n._1 + n._2)
  fibs.drop(n - 1).head
}

This compiles and streamFib returns a BigInt type (as expected?).

I also noticed a few more behaviors:

val s1:Stream[BigInt] = 1 #:: 2 #:: Stream.empty // incorrect, found Int required BigInt
val s2:Stream[BigInt] = 1 #:: 2 #:: Stream.empty[BigInt] // correct
val l1:List[BigInt] = 1 :: 2 :: List.empty[BigInt] // incorrect, found Any required BigInt
val l2:List[BigInt] = 1 :: BigInt(2) :: List.empty[BigInt] // correct

Answer 1

tl;dr:

fibs is defined as a Stream[BigInt], so when you prepend an Int to it (1 #:: ...), the compiler looks for an implicit conversion from Int to BigInt and finds it in BigInt.int2bigInt

---

---

There are a couple of things going on here.

1) The BigInt companion object defines an implicit conversion from Int to BigInt:

implicit def int2bigInt(i: Int): BigInt = apply(i)

This means that wherever you need a BigInt you can supply an Int and the implicit conversion will convert the value. You can also say that Ints can be viewed as BigInts.

2) methods that end with a colon are right-associative. This means that 1 #:: 2 #:: Stream.empty[BigInt] can be effectively rewritten as Stream.empty[BigInt].#::(2).#::(1)

---

Now, if you look at the signature of Stream.#:: (def #::(hd: A): Stream[A]) you'll see that Stream[BigInt].#::(x) can only compile if x is a BigInt.

When you call 1 #:: 2 #:: Stream.empty[BigInt] you are calling Stream[BigInt].#:: passing an Int value instead of a BigInt, but, as I mentioned earlier, Ints can be viewed as BigInts, so they are automatically converted to BigInts and everything compiles.

---

When you do this: val s1:Stream[BigInt] = 1 #:: 2 #:: Stream.empty you are doing a different thing instead: you are creating on the right hand side a Stream[Int] (Stream.empty type is inferred to be Int from the 1,2 values you pass) and then you are assigning this value to a Stream[BigInt] val.

Unfortunately, there is no implicit conversion from Stream[A] to Stream[B], even if A can be viewed as B, thus compilation fails.

You can define your own implicit conversion though:

implicit def asBigIntStream(xs: Stream[Int]): Stream[BigInt] = xs.map(BigInt.int2bigInt)
val s1:Stream[BigInt] = 1 #:: 2 #:: Stream.empty //This now works

---

There's something else going on with Lists: differently from Stream, the List cons is defined as:

def ::[B >: A] (x: B): List[B]

With Stream.#::(x) you needed x to be the exact same type as the Stream you were prepending x to. With List.::(x), instead, x (that has type B) can be an instance of a supertype of the list's type. The resulting list will be a List[B], i.e. prepending to a list can widen its type.

So, when you do 2 :: List.empty[BigInt] you're effectively Calling List[A].::(x: B) where A is BigInt and B is inferred to be Any because Any is the most strict supertype of BigInt that is also a supertype of Int.

Since this makes the compiler happy, no implicit conversions are looked for, and the resulting list is a List[Any] that you can't use anymore as a list of integers.

You can basically call whatever :: List[X] to get a List[Y] where Y is the most strict supertype of both X and the type of whatever

---

So, why doesn't val l1:List[BigInt] = 1 :: 2 :: List.empty[BigInt] work while val l2 : List[BigInt] = 1 :: BigInt(2) :: List.empty[BigInt] does?

It's because of type inference. Let's rewrite the two expressions removing the right-associativity:

val l1: List[BigInt] = (List.empty[BigInt].::(2)).::(1) // incorrect, found Any required BigInt
val l2: List[BigInt] = (List.empty[BigInt].::(BigInt(2))).::(1)  // correct

I'm not 100% sure of this (anyone please correct me if I'm wrong):

• The compiler can help the type inference only on the last application of :: (List.empty[BigInt].::(2)) is a List[Any] well before applying .::(1) so there's nothing we can do

• (List.empty[BigInt].::(BigInt(2))) is already a List[BigInt] and the compiler can try to make .::(1) a BigInt (thus looking for implicit conversions)