隐式解析失败? [英] Implicit Resolution Failure?
问题描述
I have been working on a "shapeless style" implementation of Okasaki's dense binary number system. It's simply a type-level linked-list of bits; a sort of HList
of binary Digit
s. I have completed a first draft of my ops, which include the standard math operations you'd expect for natural numbers. Only now do I realize a big problem in my encoding. How do I fix the implicit resolution in my Induction
example? Feel free to paste the entire snippet into a REPL. In this example, the only dependency on shapeless is for DepFn1
, and 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 somewhat incomplete answer, but hopefully it'll get you unstuck ...
我认为您的问题是r1
的定义
I think your problem is the definition of r1
here,
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
,这将在r1
隐式中从右向左推动推理过程.参数块.
When you ask for Induction(_2)
you're hoping for r1
to be applicable and s.Out
to be fixed as _2
and that that will drive the inference process from right to left in r1
s implicit parameter block.
不幸的是,这不会发生.首先,s.Out
不会被固定为_2
,因为它不是类型变量.因此,您至少必须将其重写为,
Unfortunately that won't happen. First, s.Out
won't be fixed as _2
because it isn't a type variable. So you would at the very least have to rewrite this as,
implicit def r1[A <: Dense, SO <: Dense]
(implicit r: Induction[A], s: Succ.Aux[A, SO]): Induction[SO] =
new Induction[SO]{}
甚至适用.但是,这不会使您更进一步,因为 for 因此,我担心您将不得不重新考虑一下.我认为您最好的方法是定义一个 So I'm afraid you'll have to rethink this a little. I think your best approach would be to define a 现在,当您要求输入 Now when you ask for 请注意,一般策略是从结果类型( Notice that the general strategy is to start with the result type ( 还要注意,我已经在隐式定义中添加了显式结果类型:您应该几乎总是这样做(此规则很少有例外). Also notice that I've added explicit result types to the implicit definitions: you should almost always do this (there are rare exceptions to this rule). 这篇关于隐式解析失败?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!SO
仅被约束为等于s
的类型成员Out
... ...在选择Succ
时不起作用s
的实例.而且我们无法从另一端取得任何进展,因为就类型检查器而言,此时A
尚未完全确定.r1
even to be applicable. This won't get you much further, however, because SO
is merely constrained to be equal to the type member Out
of s
... it doesn't play a role in the selection of the Succ
instance for s
. And we can't make any progress from the other end, because at this point A
is completely undetermined as far as the typechecker is concerned.Pred
运算符,该运算符使您可以沿着这些思路定义一些内容,Pred
operator which would allow you to define something along these lines,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
实例,从而为PO
生成_1
的解决方案,从而得到typechecker解决下一步的归纳所需的内容.Induction(_2)
S
will be solved immediately as _2
, the Pred
instance for _2
will be resolved, yielding a solution of _1
for PO
which gives the typechecker what it needs to resolve the next step of the induction.Induction[S]
)开始修复初始类型变量,然后在隐式参数列表中从左到右进行操作.Induction[S]
) to fix the initial type variable(s), and then work from left to right across the implicit parameter list.