Rogach - 16 days ago 5
Scala Question

# Is there a way to do recursive implicit def with types?

I'm trying to print peano numbers, something like this:

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

type _1 = Succ[_0]
type _2 = Succ[_1]

class RepNat[T <: Nat](val value: Int)
def rep[T <: Nat](implicit r: RepNat[T]) = r.value
implicit val repZero = new RepNat[_0](0)
implicit def repSucc[A <: Succ[B], B <: Nat](implicit r: RepNat[B]): RepNat[A] = new RepNat[A](r.value + 1)
println(rep[_0])
println(rep[_1])
// does not work, implicits do not resolve recursively:
// implicitly[RepNat[_2]]
// println(rep[_2])

// but explicit instantiation works:
println(rep[_2](repSucc(implicitly[RepNat[_1]])))
``````

Recursive implicits do work. The following definition works fine for `_2`:

``````implicit def repSucc[A <: Nat, B <: Nat](implicit
ev: A <:< Succ[B],
r: RepNat[B]
): RepNat[A] =
new RepNat[A](r.value + 1)
``````

The reason, I believe, is that `repSucc` gets a single actual type argument `A`, and needs to calculate `B` from that. With your definition it tries to assign `A` and `B` at the same time, and thus `B` gets assigned effectively to `Nothing`.

This a common problem with type inference in Scala, and the usual solution is to move the type bound `A <: M[B]` to a generalised type constraint `A <:< M[B]`.

Also, note that the order of implicit parameters matters: first the compiler calculates `B` from `A` with `ev: A <:< Succ[B]`, and then finds the `RepNat` implementation for `B`, possibly recursively.