隐式解析失败？

Question

我一直在研究 "shapeless style" Okasaki's dense binary number system 的实现。它只是一个类型级别的位链接列表；一种 HList 的二进制 Digit。我已经完成了我的操作的初稿，其中包括您期望的自然数标准数学运算。直到现在我才意识到我的编码有一个大问题。如何修复 Induction 示例中的隐式解析？随意将整个片段粘贴到 REPL 中。在此示例中，对 shapeless 的唯一依赖是 DepFn1 和 DepFn2.

import shapeless.{ DepFn1, DepFn2 }

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

sealed trait Dense { type N <: Dense }

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

sealed trait DNil extends Dense {
  type N = DNil
}

case object DNil extends DNil

/* ops */
trait IsDCons[N <: Dense] {
  type H <: Digit
  type T <: Dense

  def digit(n: N): H
  def tail(n: N): T
}

object IsDCons {
  type Aux[N <: Dense, H0 <: Digit, T0 <: Dense] = IsDCons[N] {
    type H = H0
    type T = T0
  }

  def apply[N <: Dense](implicit ev: IsDCons[N]): Aux[N, ev.H, ev.T] = ev

  implicit def isDCons[H0 <: Digit, T0 <: Dense]: Aux[H0 :: T0, H0, T0] =
    new IsDCons[H0 :: T0] {
      type H = H0
      type T = T0

      def digit(n: H0 :: T0): H = n.digit
      def tail(n: H0 :: T0): T = n.tail
    }
}

// Disallows Leading Zeros
trait SafeCons[H <: Digit, T <: Dense] extends DepFn2[H, T] { type Out <: Dense }

trait LowPrioritySafeCons {
  type Aux[H <: Digit, T <: Dense, Out0 <: Dense] = SafeCons[H, T] { type Out = Out0 }

  implicit def sc1[H <: Digit, T <: Dense]: Aux[H, T, H :: T] =
    new SafeCons[H, T] {
      type Out = H :: T
      def apply(h: H, t: T) = h :: t
  }
}

object SafeCons extends LowPrioritySafeCons {
  implicit val sc0: Aux[Zero.type, DNil, DNil] =
    new SafeCons[Zero.type, DNil] {
      type Out = DNil
      def apply(h: Zero.type, t: DNil) = DNil
  }
}

trait ShiftLeft[N <: Dense] extends DepFn1[N] { type Out <: Dense }

object ShiftLeft {
  type Aux[N <: Dense, Out0 <: Dense] = ShiftLeft[N] { type Out = Out0 }

  implicit def sl1[T <: Dense](implicit sc: SafeCons[Zero.type, T]): Aux[T, sc.Out] =
    new ShiftLeft[T] {
      type Out = sc.Out
      def apply(n: T) = Zero safe_:: n
    }
}

trait Succ[N <: Dense] extends DepFn1[N] { type Out <: Dense }

object Succ {
  type Aux[N <: Dense, Out0 <: Dense] = Succ[N] { type Out = Out0 }

  def apply[N <: Dense](implicit succ: Succ[N]): Aux[N, succ.Out] = succ

  implicit val succ0: Aux[DNil, One.type :: DNil] =
    new Succ[DNil] {
      type Out = One.type :: DNil
      def apply(DNil: DNil) = One :: DNil
    }

  implicit def succ1[T <: Dense]: Aux[Zero.type :: T, One.type :: T] =
    new Succ[Zero.type :: T] {
      type Out = One.type :: T
      def apply(n: Zero.type :: T) = One :: n.tail
  }

  implicit def succ2[T <: Dense, S <: Dense]
    (implicit ev: Aux[T, S], sl: ShiftLeft[S]): Aux[One.type :: T, sl.Out] =
      new Succ[One.type :: T] {
        type Out = sl.Out
        def apply(n: One.type :: T) = n.tail.succ.shiftLeft
      }
}

/* syntax */
val Cons = ::
implicit class DenseOps[N <: Dense](val n: N) extends AnyVal {
  def ::[H <: Digit](h: H): H :: N = Cons(h, n)

  def safe_::[H <: Digit](h: H)(implicit sc: SafeCons[H, N]): sc.Out = sc(h, n)

  def succ(implicit s: Succ[N]): s.Out = s(n)

  def digit(implicit c: IsDCons[N]): c.H = c.digit(n)

  def tail(implicit c: IsDCons[N]): c.T = c.tail(n)

  def shiftLeft(implicit sl: ShiftLeft[N]): sl.Out = sl(n)
}

/* aliases */
type _0 = DNil
val _0: _0 = DNil

val _1 = _0.succ
type _1 = _1.N

val _2 = _1.succ
type _2 = _2.N

/* test */
trait Induction[A <: Dense]

object Induction{
  def apply[A <: Dense](a: A)(implicit r: Induction[A]) = r
  implicit val r0 = new Induction[_0] {}
  implicit def r1[A <: Dense](implicit r: Induction[A], s: Succ[A]) = 
    new Induction[s.Out]{}
}

Induction(_0)
Induction(_1)
Induction(_2) // <- Could not find implicit value for parameter r...

This is a link to the question's follow up

Answer 1

这个答案有点不完整，但希望它能让你摆脱困境...

我认为你的问题是这里r1的定义，

object Induction{
  def apply[A <: Dense](a: A)(implicit r: Induction[A]) = r
  implicit val r0 = new Induction[_0] {}
  implicit def r1[A <: Dense](implicit r: Induction[A], s: Succ[A]) = 
    new Induction[s.Out]{}
}

当您要求 Induction(_2) 时，您希望 r1 适用并且 s.Out 固定为 _2，这将推动推理过程在 r1s 隐式参数块中从右到左。

不幸的是，这不会发生。首先，s.Out 不会固定为 _2 因为它不是类型变量。所以你至少必须将其重写为，

implicit def r1[A <: Dense, SO <: Dense]
  (implicit r: Induction[A], s: Succ.Aux[A, SO]): Induction[SO] = 
    new Induction[SO]{}

对于r1甚至是适用的。但是，这不会让您走得更远，因为 SO 仅被限制为等于 s 的类型成员 Out ...为 s 选择 Succ 实例。而且我们无法从另一端取得任何进展，因为此时 A 就类型检查器而言完全未确定。

所以恐怕你得重新考虑一下。我认为你最好的方法是定义一个 Pred 运算符，它允许你按照这些行定义一些东西，

implicit def r1[S <: Dense, PO <: Dense]
  (implicit p: Pred.Aux[S, PO], r: Induction[PO]): Induction[S] = 
    new Induction[S]{}

现在，当您请求 Induction(_2) S 时，_2 将立即被解决，_2 的 Pred 实例将被解决，产生一个_1 对 PO 的解决方案，它为类型检查器提供了解析下一步归纳所需的内容。

请注意，一般策略是从结果类型 (Induction[S]) 开始固定初始类型变量，然后从左到右遍历隐式参数列表。

另请注意，我已将显式结果类型添加到隐式定义中：您几乎应该始终这样做（这条规则很少有例外）。

隐式解析失败？

Implicit Resolution Failure?

scala

type-level-computation

shapeless