为什么折叠推断任何？

Question

我正在使用 Scala 2.11.12 和这个声明进行编译：

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
    }
  }

给出：

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

在这个项目中编写折叠时，我已经处理过很多次这样的事情（第一个在 Scala 中），我总是找到一种不同的方法来让它工作，但也许如果我理解它我会停止打这堵墙。

Answer 1

因为你需要使用foldLeft而不是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
    }
  }

斯卡蒂：https://scastie.scala-lang.org/VzfKqHZ5QJyNPfwpLVGwSw

fold 不起作用，因为它是语义的：fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1 - 因此在您的情况下 zipWithIndex 给出 (Int, Int) 类型而不是预期的 Int 和函数在 returns Int 中 - 所以最后推断类型你会看到 Any - (Int, Int) 和 Int 之间的共同祖先。

而 foldLeft[Z](zero: Z) 推断出 Int 因为你给出 0

Answer 2

fold 方法期望关联二元运算作为其第二个参数，即满足

的某些运算f(_, _)

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

您的折叠函数 f 结合了 Int 和 (Int, Int)。它不能是关联的，因为 f(x, f(y, z)) 和 f(f(x, y), z) 不可能同时进行类型检查：

如果 f(x, f(y, z)) 类型检查，则 x: Int 和 f(y, z): (Int, Int),
但是，f的return类型必须是(Int, Int)，
但是，f(f(x, y), z) 无法进行类型检查，因为它在第一个参数中得到 (Int, Int)，而预期的是 Int。

因此，在这里谈论结合性是没有意义的：这个说法甚至都不是假的，根本无法首先说明。

由于操作不是关联的，你不能简单地让语言来决定以什么顺序处理元素；你必须select一个折叠方向，即决定是否

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

(向左折叠)

或

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

(向右折叠)

在你的情况下，它必须是 foldLeft。

类型 Any 被推断为 Int 和 (Int, Int) 之间的最小上限，因为编译器试图将 f 解释为关联操作，它必然有两个相同类型的参数。

为什么折叠推断任何？

Why fold infers Any?

scala

types

type-inference

fold

type-mismatch