Rogach 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]])))

Answer

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.

Comments