Type mismatch in Scala's for-comprehension

I have tried to define a recursive Scala function that looks something like this:

def doSomething: (List[List[(Int, Int)]], List[(Int, Int)], Int, Int) => List[Int] =
(als, rs, d, n) =>
if (n == 0) {
for (entry <- rs if (entry._1 == d)) yield entry._2
} else {
for (entry <- rs; adj <- als(entry._1)) yield doSomething(als, rs.::((adj._1, adj._2 + entry._2)), d, n - 1)
}


Now, the compiler tells me:

| | | | | | <console>:17: error: type mismatch;
found : List[List[Int]]
required: List[Int]
for (entry <- rs; adj <- als(entry._1)) yield doSomething(als, rs.::((adj._1, adj._2 + entry._2)), d, n - 1)
^

| | | | | | <console>:17: error: type mismatch;
found : List[List[Int]]
required: List[Int]
for (entry <- rs; adj <- als(entry._1)) yield doSomething(als, rs.::((adj._1, adj._2 + entry._2)), d, n - 1)
^

I cannot figure out what the problem is. I'm sure that I'm using <- correctly. On the other hand, I'm a Scala newbie coming from the Java world...

<-

Regarding the types of the input:

als : List[List[(Int,Int)]],

als

List[List[(Int,Int)]]

rs : List[(Int,Int)],

rs

List[(Int,Int)]

d and n : Int

d

n

Int

The compiler error appears as soon as I tell IntelliJ to send my code to the Scala console.

(List[List[(Int, Int)]], List[(Int, Int)], Int, Int)

List[Int]

=>

als

List[List[(Int, Int)]]

rs

List[(Int, Int)]

d

n

Int

[scala]

def

List

2 Answers
2

When you yield an A when iterating on a List, you return a List[A]. doSomething returns a List[Int], so by yielding that you return a List[List[Int]]. You can unroll that like this:

yield

A

List

List[A]

doSomething

List[Int]

List[List[Int]]

def doSomethingElse(als: List[List[(Int, Int)]], rs: List[(Int, Int)], d: Int, n: Int): List[Int] =
if (n == 0) {
for ((k, v) <- rs if k == d) yield v
} else {
for {
(k, v) <- rs
(adjk, adjv) <- als(k)
item <- doSomethingElse(als, (adjk, adjv + v) :: rs, d, n - 1)
} yield item
}


Notice that I also used a method notation for brevity and destructured the pairs and leveraged the right-associativity of methods whose name ends in : for readability, feel free to use whatever convention you might want (but I don't see really a reading why having a method that returns a constant function (maybe you'd want to just use a val to declare it).

:

val

As a further note, you are using random access on a linear sequence (als(k)), you may want to consider an indexed sequence (like a Vector). More info on the complexity characteristics of the Scala Collection API can be found here.

als(k)

Vector

for test purpose I created some sample data that meets the input datatypes as

val als = List(List((1,2), (3,4)), List((1,2), (3,4)), List((1,2), (3,4)))
//als: List[List[(Int, Int)]] = List(List((1,2), (3,4)), List((1,2), (3,4)), List((1,2), (3,4)))
val rs = List((1,2), (2,3))
//rs: List[(Int, Int)] = List((1,2), (2,3))
val d = 1
//d: Int = 1
val n = 3
//n: Int = 3


And in you doSomething function when n == 0 you are doing

n == 0

for (entry <- rs if (entry._1 == d)) yield entry._2
//res0: List[Int] = List(2)


You can see that the return type is List[Int]

List[Int]

And for the else part you are calling recursively doSomething.

I have created dummy doSomething method of yours as your doSomething function definition lacks input variables as

doSomething

def dosomething(nn: Int)={
for (entry <- rs if (entry._1 == d)) yield entry._2
}


and I call the method recursively as

for (entry <- rs; adj <- als(entry._1)) yield dosomething(0)
//res1: List[List[Int]] = List(List(2), List(2), List(2), List(2))


Clearly you can see that the second nested for loop is returning List[List[Int]]

List[List[Int]]

And thats what the compiler is warning you

error: type mismatch;
found : List[List[Int]]
required: List[Int]

error: type mismatch;
found : List[List[Int]]
required: List[Int]

I hope the answer is helpful

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.