Why fold infers Any?

Question

I'm compiling with Scala 2.11.12 and this declaration:

import scala.collection.mutable.Stack
def stackToInt(stack: Stack[Int]): Int =
  stack.zipWithIndex.fold(0){ case (z: Int, (piece: Int, index: Int)) =>
    piece match {
      case 1 => (1 << index) + z
      case _ => z
    }
  }

gives:

stack.zipWithIndex.fold(0){ case (z: Int, (piece: Int, index: Int)) =>
                       ^
error: type mismatch;
        found   : Any
        required: Int

I've been dealing with stuff like this many times when writing folds in this project (first one in Scala) and I always found a different way to make it work, but maybe if I understand it I will stop hitting this wall.

Answer 1

The fold method expects an associative binary operation as its second argument, i.e. some operation f(_, _) that satisfies

f(x, f(y, z)) = f(f(x, y), z)

Your folding function f combines an Int with an (Int, Int). It cannot be associative, because f(x, f(y, z)) and f(f(x, y), z) cannot possibly type-check at the same time:

• If f(x, f(y, z)) typechecks, then x: Int and f(y, z): (Int, Int),
• But then, the return type of f must be (Int, Int),
• But then, f(f(x, y), z) cannot typecheck, because it gets (Int, Int) in the first argument, where an Int is expected.

Therefore, it's not meaningful to talk about associativity here: the claim is not even false, it simply cannot be stated in the first place.

Since the operation is not associative, you cannot simply leave it to the language to decide in what order to process the elements; you must select a folding direction, i.e. decide whether it's

f(...f(f(f(a0, x1), x2), x3)...)

(foldLeft)

or

f(...f(x(n-3), f(x(n-2), f(x(n-1), a0))...)))))

(foldRight)

In your case, it must be foldLeft.

The type Any is inferred as the least upper bound between Int and (Int, Int), because the compiler is attempting to interpret the f as an associative operation, which, necessarily, has two parameters of the same type.

Answer 2

Because you need to use foldLeft instead of fold:

import scala.collection.mutable.Stack
def stackToInt(stack: Stack[Int]): Int =
  stack.zipWithIndex.foldLeft(0) { case (z: Int, (piece: Int, index: Int)) =>
    piece match {
      case 1 => (1 << index) + z
      case _ => z
    }
  }

Scatie: https://scastie.scala-lang.org/VzfKqHZ5QJyNPfwpLVGwSw

fold does not work because it's semantic: fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1 - hence in your case zipWithIndex gives (Int, Int) type instead of expected Int, and function inside returns Int - so at the end infered type you see Any - common ancestor between (Int, Int) and Int.

And foldLeft[Z](zero: Z) has infers Int because you give 0