求和 "Large" Nat's

Question

鉴于：

scala> import shapeless.nat.
_0   _10   _12   _14   _16   _18   _2    _21   _3   _5   _7   _9      natOps            
_1   _11   _13   _15   _17   _19   _20   _22   _4   _6   _8   apply   toInt             

scala> import shapeless.ops.nat._
import shapeless.ops.nat._

> 3 分钟后，下面的代码没有 compiled/run。这是为什么？

scala> Sum[_22, _22]

另外，看看上面的REPL自动补全，_44是否存在于shapeless中？

Answer 1

为什么这么慢？

让我们从较小的数字开始。当你请求 Sum[_4, _4] 时，编译器会去寻找一个实例，它会找到 these two methods:

implicit def sum1[B <: Nat]: Aux[_0, B, B] = new Sum[_0, B] { type Out = B }
implicit def sum2[A <: Nat, B <: Nat](implicit
  sum: Sum[A, Succ[B]]
): Aux[Succ[A], B, sum.Out] = new Sum[Succ[A], B] { type Out = sum.Out }

显然第一个已经过时了，因为 _4 不是 _0。它知道 _4 与 Succ[_3] 相同（稍后会详细介绍），因此它将尝试 sum2 with A as _3 and B 作为 _4.

这意味着我们需要找到一个 Sum[_3, _5] 实例。 sum1 出于与之前类似的原因，所以我们再次尝试 sum2，这次使用 A = _2 和 B = _5，这意味着我们需要一个 Sum[_2, _6]，这让我们回到 sum2，A = _1 和 B = _6，这让我们寻找 Sum[_1, _7]。这是我们最后一次使用 sum2，以及 A = _0 和 B = _7。这次当我们去寻找 Sum[_0, _8] 时，我们会点击 sum1，然后我们就完成了。

所以很明显，对于 n + n 我们将不得不进行 n + 1 隐式搜索，并且在每次搜索期间，编译器将进行类型相等性检查和其他事情（更新：请参阅 Miles 的回答，以了解这里最大的问题是什么）需要遍历 Nat 类型的结构，因此我们处于指数级区域。编译器真的，真的不是为了有效地处理这样的类型而设计的，这意味着即使对于小数字，这个操作也会花费很长时间。

旁注 1：Shapeless 中的实现

我不明白为什么 sum2 不是这样定义的：

implicit def sum2[A <: Nat, B <: Nat](implicit
  sum: Sum[A, B]
): Aux[Succ[A], B, Succ[sum.Out]] = new Sum[Succ[A], B] { type Out = Succ[sum.Out] }

这要快得多，至少在我的机器上是这样，Sum[_18, _18] 在四秒内完成编译，而不是七分钟，而且还在增加。

旁注 2：归纳启发法

这似乎不是 Typelevel Scala 的 -Yinduction-heuristics 有帮助的情况——我只是尝试用 Sum 上的 @inductive 注释编译 Shapeless，它看起来仍然非常准确和没有它一样慢得可怕。

44 呢？

_1、_2、_3 类型别名是在 this boilerplate generator 在 Shapeless 中生成的代码中定义的，它被配置为仅生成最多 22 的值。具体来说，在这种情况下，这是一个完全任意的限制。我们可以这样写，例如：

type _23 = Succ[_22]

我们所做的与代码生成器所做的完全相同，但更进一步。

不过，Shapeless 的 _N 别名止于 22 并不重要，因为它们只是别名。 Nat 的重要之处在于它的结构，它独立于我们可能为它起的任何好听的名字。即使 Shapeless 根本不提供任何 _N 别名，我们仍然可以编写这样的代码：

import shapeless.Succ, shapeless.nat._0, shapeless.ops.nat.Sum

Sum[Succ[Succ[_0]], Succ[Succ[_0]]]

这和写 Sum[_2, _2] 完全一样，只是打字更烦人。

因此，当您编写 Sum[_22, _22] 时，编译器在表示结果类型时不会遇到任何问题（即 _0 周围的 44 Succs），即使它没有没有 _44 类型别名。

Answer 2

根据 Travis 的出色回答，问题的根源似乎是 sum2 定义中成员类型的使用。使用以下 Sum 及其实例的定义，

trait Sum[A <: Nat, B <: Nat] extends Serializable { type Out <: Nat }

object Sum {
  def apply[A <: Nat, B <: Nat](implicit sum: Sum[A, B]): Aux[A, B, sum.Out] = sum

  type Aux[A <: Nat, B <: Nat, C <: Nat] = Sum[A, B] { type Out = C }

  implicit def sum1[B <: Nat]: Aux[_0, B, B] = new Sum[_0, B] { type Out = B }
  implicit def sum2[A <: Nat, B <: Nat, C <: Nat]
    (implicit sum : Sum.Aux[A, Succ[B], C]): Aux[Succ[A], B, C] =
      new Sum[Succ[A], B] { type Out = C }
}

它用一个额外的类型变量替换了成员类型的使用，编译时间在我的机器上是 0+噪音，无论有没有 -Yinduction-heurisitics。

我认为我们看到的问题是使用成员类型进行子类型化的病态案例。

除此之外，归纳是如此之小，以至于我实际上不希望 -Yinduction-heurisitics 做出很大的改进。

现在更新 fixed in shapeless。

求和 "Large" Nat's

Summing "Large" Nat's

scala

shapeless

为什么这么慢？

旁注 1：Shapeless 中的实现

旁注 2：归纳启发法

44 呢？