CODEWITHSUNDEEP
scala
HamoriZ
HamoriZ

Reputation: 2438

Return type of recursive function

What is the general type of fs? 

 lazy val fs  = List(2,3,4).zip(fs.tail)

The compiler asks for setting it at compile time.

Update: I wanted to consider a solution of the 2nd Project Euler problem:

    lazy val fs: Stream[Int] =
      0 #:: 1 #:: fs.zip(fs.tail).map(p => p._1 + p._2)

   fs.view.takeWhile(_ <= 4000000).filter(_ % 2 == 0).sum

I just wanted to debug what happens at these steps

Upvotes: 3

Views: 707

Answers (3)

Emil L
Emil L

Reputation: 21081

The following compiles, but accessing fs generates a StackOverflowError because of the definitions recursize nature.

lazy val fs:List[Product] = List(2,3,4).zip(fs.tail)

If we wanted to be more specific about the type we could do something like:

lazy val fs:List[(Int, (Int, Product))] = List(2,3,4).zip(fs.tail)

The typle is not Nothing. Since the following does not compile:

scala> lazy val fs:Nothing = List(2,3,4).zip(fs.tail)
<console>:8: error: value tail is not a member of Nothing
   lazy val fs:Nothing = List(2,3,4).zip(fs.tail)

Similar type errors occur if we define fs as List[Nothing],List[(Int, Nothing)] etc etc. So clearly the type of the expression is a List of Product. Now if we use Stream instead we can make something that does not cause a runtime error:

scala> lazy val fs:Stream[Any] = 0 #:: 1 #:: fs.zip(fs.tail).map(p => p:Any)
fs: Stream[Any] = <lazy>

scala> fs take 5 foreach println
0
1
(0,1)
(1,(0,1))
((0,1),(1,(0,1)))

Upvotes: 2

pedrofurla
pedrofurla

Reputation: 12783

I don't think this possible in a type safe way, look:

scala> lazy val fs=List(1,2,3).zip(fs.tail)
<console>:7: error: recursive lazy value fs needs type
       lazy val fs=List(1,2,3).zip(fs.tail)
                                   ^

scala> lazy val fs:List[(Int,Int)]=List(1,2,3).zip(fs.tail)
<console>:7: error: type mismatch;
 found   : List[(Int, (Int, Int))]
 required: List[(Int, Int)]
       lazy val fs:List[(Int,Int)]=List(1,2,3).zip(fs.tail)

At least I can't see how to achieve any useful result. What is your intention?

On the other hand we can do this:

scala> val l = List(1,2,3)
l: List[Int] = List(1, 2, 3)

scala> val fs = l.zip(l.tail)
fs: List[(Int, Int)] = List((1,2), (2,3))

Is it your desired result?

Upvotes: 0

Didier Dupont
Didier Dupont

Reputation: 29528

I don't think there is a most precise type that would describe it. Of course, it cannot be computed, so the actual type would be Nothing.

If we forget about the implicit canBuildFrom, the signature of zip in List[A] would be

def zip[B](l: List[B]) : List[(A,B)]

Starting with A = Int, it is clear that we have a List[(Int, B)], without even considering that the argument of zip is fs.tail. If we add that knowledge, we now have List[(Int, (Int, B))] and we can loop from there, you can type it List[(Int,(Int, (Int, _)))] and nest as many levels as you want.

I believe there is no way to express that most precise type (nesting to infinite) in scala. Anyway, it is not inhabited, this type contains no value, and fs cannot be computed.

Upvotes: 5

Related Questions