Thanks to @MilesSabin's answer I can write a type level Fibonacci sequence:

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

What I'd really like to be able to do is get a Witness for Dense and use it like:

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

Scala tells me that it can't summon a Witness instance. I'm guessing this is because my type-level encoding of natural numbers is a linked list of bits and that's not a singleton type. I can't understand why Witness won't work since there is only a single inhabitant for a class like _7.

What I'm trying to do is materialize a value for a type that only has one possible value. That way I can get an Out directly from apply.

I think a possible solution might leverage implicit macros.

Any and all ideas are welcome. I encourage you to leave a note if the question isn't clear.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.