具体化只有一个居民的类型的价值

Question

感谢@MilesSabin的answer我可以编写类型级别的斐波那契序列：

sealed trait Digit
case object Zero extends Digit
case object One extends Digit

sealed trait Dense { type N <: Dense }
sealed trait DNil extends Dense { type N = DNil }
case object DNil extends DNil
final case class ::[+H <: Digit, +T <: Dense](digit: H, tail: T) extends Dense {
  type N = digit.type :: tail.N
}

/* The `A`th Fibonacci number is `B` */
trait Fib[A <: Dense, B <: Dense]

object Fib {
  implicit val f0 = new Fib[_0, _0] {}
  implicit val f1 = new Fib[_1, _1] {}

  implicit def f2[A <: Dense, P <: Dense, P2 <: Dense, F <: Dense, F2 <: Dense]
   (implicit p: Pred.Aux[A, P],
             p2: Pred.Aux[P, P2],
             f: Fib[P, F],
             f2: Fib[P2, F2],
             sum: Sum[F, F2]): Fib[A, sum.Out] = new Fib[A, sum.Out] {}
}

implicitly[Fib[_7, _13]]

我真正想做的是为

Witness

获得

Dense

并像这样使用它：

def apply[Out <: Dense](n: Dense)(implicit f:Fib[n.N, Out], w:Witness.Aux[Out]): Out
  = w.value

Scala 告诉我它无法召唤

Witness

实例。我猜这是因为我的自然数类型级编码是位的链接列表，而不是单例类型。我不明白为什么

Witness

不起作用，因为像

_7

这样的班级只有一个居民。

我想做的是为只有一个可能值的类型具体化一个值。这样我就可以直接从

Out

获得

apply

。

我认为可能的解决方案可能会利用隐式宏。

欢迎任何和所有的想法。如果问题不清楚，我鼓励您留言。

Answer 1

我认为你的问题是

Witness

设计用于在编译时完全已知的类型并且是 单例类型。基本上，这意味着只有一种可能值的类型。在您的情况下，您的

Dense

类型（一种位链接列表）实际上并不像单例类型一样，因为 Scala 无法静态地告诉您特定的

Dense

实际上只代表一个数字。

enter code here

1.选择密集的单例类型

如果您可以将

Dense

类型转换为单例类型，那么

Witness

处理它们将毫无困难。您可能希望通过更明确地设置每个

Dense

类型来使其成为真正的单例。请记住，由于

Dense

将数字显示为

Digit

的链接列表，因此在此处使用单例类型而不弄乱类型本身可能会很棘手。

2.使用 Shapeless 的

Witness

进行一些类型转换

由于您使用类型来显示数字，请确保这些类型在编译时得到整理并且可以实际使用。 Shapeless 的

Witness

与单例类型配合得很好，但你必须确保也将

Dense

类型视为单例。

我们的方法手动构造每个

Dense

数字的单例表示。这很乏味，但可以让

Witness

正常工作。

import shapeless.Witness
import shapeless.syntax.singleton._

trait Fib[A <: Dense, B <: Dense] {
  def value: B
}

object Fib {
  implicit val fib0: Fib[_0, _0] = new Fib[_0, _0] { def value = _0 }
  implicit val fib1: Fib[_1, _1] = new Fib[_1, _1] { def value = _1 }

  implicit def fibN[A <: Dense, P <: Dense, P2 <: Dense, F <: Dense, F2 <: Dense]
   (implicit p: Pred.Aux[A, P],
             p2: Pred.Aux[P, P2],
             f: Fib[P, F],
             f2: Fib[P2, F2],
             sum: Sum[F, F2]): Fib[A, sum.Out] = new Fib[A, sum.Out] {
    def value = sum.value
  }
}

// An example Dense number as a type
val _7 = Witness[_7].value

3.隐式召唤宏

如果早期的解决方案不适合您或感觉有点太复杂，您可能需要查看宏。它们为您在编译时提供了更大的灵活性来处理和创建隐式证据。这样，您就可以根据

Witness

的结构来创建

Dense

（或类似的东西）的实例。事实上，Shapeless 使用宏来处理其类型级别的内容。

您可以尝试一下这种伪代码，在其中专门为类型

Witness

:

 创建 

Out

import scala.reflect.macros.blackbox.Context

object FibMacro {

def witnessImpl[A <: Dense](c: Context): c.Tree = {

import c.universe._

// Implement logic here to generate a Witness based on A

// For example, find the singleton representation of A, and return it

}



implicit def materializeWitness[A <: Dense]: Witness.Aux[A] = macro witnessImpl[A]

}

这个宏本质上会在编译时检查

A

的结构，并为

Witness

生成适当的隐式证据。

解决此问题的另一种方法是重新考虑您的

Dense

编码。您可能希望对数字进行编码，以便可以更轻松地将它们视为单一类型或类型级别的唯一值。例如，您可以直接将数字表示为

Nat

，而不是使用数字链接列表，这样可以使事情变得更简单。