Recursive value needs type

Question
1

I don’t understand the compiler error that says the recursive value mt needs type. Is mt really a recursive value?

    (2 to 12).foreach { j =>
      for {
        i <- (0 to 1 << j - 1)
        mt = minTerm(j, i)
        _ = assert(mt.length == j)
        _ = assert(mt.toSet.size == j)
        posBits = mt.filter(_ > 0)       // this is line 45
        j = posBits.foldLeft(0) { (acc: Int, k: Int) =>
          acc + (if (k > 0) math.pow(2, k - 1).toInt else 0)
        }
      } assert(j == i, s"failed for j=$j i=$i posBits=$posBits")
    }

Here’s the error.

Error:(45, 9) recursive value mt needs type
        posBits = mt.filter(_ > 0)

BTW minTerm is a function which returns List[Int]

object BitFiddle {

  private val prng = scala.util.Random

  def minTerm(n: Int, i: Long): List[Int] = {
    // Calculate the minTerm as a list of positive and negative integers.
    // View i as an n-bit integer.  Look at each bit in that integer.
    // If the j'th bit is 0, take j, else take -j, and build a list
    //   of these +/1 j's.
    // E.g., if n=3 and i=6, that's binary 110; so build the list
    //    List(3, 2, -1).  The list is actually built with the most
    //    significant bit at the left, and least significant at the right.
    // Each minTerm contains all the integers 1 <= |i| < n in either their
    // positive or negative form.  I.e., if n=3, then such a minTerm is
    // List(3,-2,1) but List(3,-3,2,1) is not and List(3,1) is not.

    val nil: List[Int] = Nil

    (1 to n).foldLeft((nil, i)) { case ((stack: List[Int], bitMask), position) =>
      ((if (bitMask % 2 == 1)
        position
      else
        -position) :: stack, bitMask / 2)
    }._1
  }
...
}
2

I think I see the problem. It is a misleading (wrong) compiler error. The problem is that j is defined twice. Once in the outer loop, and once in j = posBits.... If I change the name of one of the js, the error goes away.

Is this compiler error seem correct?

3

Another example the i and j binding seem to work intuitively.

(1 to 3).foreach{j =>
  for{
    i <- 0 to j
    j = i + 3
  } yield  println(s"i=$i j=$j")}

This code prints the following as expected

i=0 j=3
i=1 j=4
i=0 j=3
i=1 j=4
i=2 j=5
i=0 j=3
i=1 j=4
i=2 j=5
i=3 j=6
4

There does seem to be something fishy here though. The following code complains about a variable x which I’m not using.

(1 to 3).foreach{j =>
  for{
    i <- 0 to j
    _ = assert(j > 0)
    j = i + 3
  } yield println(s"i=$i j=$j")
}

Error:(4, 20) forward reference extends over definition of value x$1
_ = assert(j > 0)
5

I’m not entirely sure, what’s going on, but x$1 is a name for an anonymous variable, i.e. the _ in your code.
I suspect that the code resulting from desugaring the for-comprehension into map and flatMap calls makes the second and third line be in the same scope (as assignments in for do not cause another flatMap call), and in that scope, the j you assign to shadows the outer j. As the j in the assert is in the same scope, it tries to use the shadowed variable, which is only declared at a later line.

I don’t know what causes the “recursive value” error, but I’d suggest looking at the desugared for comprehension (e.g. using scalac or IntelliJ).

Overall, I’d recommend not shadowing variables. Having the meaning and scope of a variable name change in the middle of a comprehension is also difficult to understand while reading.

6

Ahh apparently all the assignments on consecutive lines are in the same scope.
But it is also surprising that _= causes a var (oops should have said val, not var here) declaration. Shouldn’t that desugar to just the assert(j>0) rather than a val ... ? Otherwise there is a risk to report variables to the user which he didn’t declare nor use?

7

Looks like it is possible to force each assigning into a new scope by using <- Some.. rather than =. E.g.,

(1 to 3).foreach{j =>
  for{
    i <- 0 to j
    _ = assert(j > 0)
    j <- Some( i + 3)
  } yield println(s"i=$i j=$j")
}
8

I don’t see a generated var declaration.

for {
  i <- (1 to 10)
  _ = assert(i > 0)
  j = i + 3
} yield j

desugars to

(1 to 10)
.map(i => {
    val x$1 = assert(i > 0)
    val j = i + 3
    (i, x$1, j)
})
.map(x$2 => x$2 match {
  case (i, _, j) => j
})
9

Did I say var? I don’t see where. But sorry if I did. I either meant variable in the generic sense or I meant to say val.

10

Nevermind that though.

I agree that the errors/warnings you see are scalac bugs. I know there are related known issues. Whether this specific one is a known issue I don’t know exactly. I’ll attempt to minimize and report later.

1 Like
11

This brings up a tangent of something that I find confusing in Scala. In Scheme and also OCaml, if I reference a variable named x inside a new declaration of a variable named x, then the value does not accidentally reference the newly declared variable. If you want that meaning, you have to do something special, (i.e., in Scheme you have to use letrec rather than let).

I’ve been bitten by this several times in Scala. That the following is a recursive reference is surprising.

def g(x:Int=>Int,i:Int) = {
  val x = (y=>x(i))
   ...
}

If the types happen to violate my assumptions then the compiler will of course complain. But if the usage x(i) is type-valid, then it’s just wrong code but would compile correctly.

12

I’ve fallen in that trap a bunch of times too. A separate keyword to allow recursive access to the name x is a bridge to far for me, though a (linter) warning "recursive value x shadows x of the same type Int => Int in enclosing scope" would be neat.

13

Note that this one is a pretty common gotcha. In my experience, 95% of the time, that “recursive value” error is actually an accidentally re-declared variable.

1 Like