整数和 Peano 自然数之间的双向转换

Question

我在 Scala 中使用自然数的标准类型编码。为了这个问题的目的，下面的定义就可以了：

sealed trait Nat
sealed trait _0 extends Nat
sealed trait Succ[N <: Nat] extends Nat

我可以使用编译器将这些 Nat 类型转换为实际数字，例如通过定义

class NatConverter[N <: Nat](val n: Int)

implicit val zeroConv: NatConv[_0] = new NatConv(0)
implicit def succConv[N <: Nat](implicit ev: NatConv[N]): NatConv[Succ[N]] =
  new NatConv(ev.n + 1)

def nat2value[N <: Nat](implicit ev: NatConv[N]) = ev.n

这个有效：

type _1 = Succ[_0]
type _2 = Succ[_1]
nat2value[_2] // gives 2

我试图通过利用依赖方法 return 类型来反转这种对应关系，如果可能的话。因此，首先需要的是 Int 和 Nat

的容器

trait Pair {
    type N <: Nat
    def n: Int
}

现在，我希望能够将 Int 隐式转换为 Pair 的实例，并为 N 设置正确的值。在这里

implicit def int2pair(a: Int): Pair =
    if (a == 0) new Pair {
        type N = _0
        val n = 0
    }
    else {
        val previous = int2pair(a - 1)
        new Pair {
            type N = Succ[previous.N]
            val n = a
        }
    }

这确实编译。不幸的是

val two = int2pair(2)
implicitly[two.N =:= _2]

失败，以及

val two = int2pair(2)
implicitly[two.N <:< _2]

知道为什么吗？

Answer 1

因为 int2pair 的 return 类型 只是 Pair，而不是 Pair { type N = _2 }。 if/else 发生在运行时，编译器无法知道将采用哪个分支。

据我所知，从值到类型的唯一方法是使用宏。你可能想看看 shapeless' singleton support.

整数和 Peano 自然数之间的双向转换

Two-way conversion between integers and Peano naturals

scala

types

dependent-type

path-dependent-type