title: Materialize the Value for a Type that has One Inhabitant
body: <p>Thanks to @MilesSabin's <a href="https://stackoverflow.com/a/32157259/867671">answer</a> I can write a type level Fibonacci sequence:</p>
  
  <pre><code>sealed trait Digit
  case object Zero extends Digit
  case object One extends Digit
  
  sealed trait Dense { type N &lt;: Dense }
  sealed trait DNil extends Dense { type N = DNil }
  case object DNil extends DNil
  final case class ::[+H &lt;: Digit, +T &lt;: Dense](digit: H, tail: T) extends Dense {
    type N = digit.type :: tail.N
  }
  
  /* The `A`th Fibonacci number is `B` */
  trait Fib[A &lt;: Dense, B &lt;: Dense]
  
  object Fib {
    implicit val f0 = new Fib[_0, _0] {}
    implicit val f1 = new Fib[_1, _1] {}
  
    implicit def f2[A &lt;: Dense, P &lt;: Dense, P2 &lt;: Dense, F &lt;: Dense, F2 &lt;: 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]]
  </code></pre>
  
  <p>What I'd really like to be able to do is get a <code>Witness</code> for <code>Dense</code> and use it like:</p>
  
  <pre><code>def apply[Out &lt;: Dense](n: Dense)(implicit f:Fib[n.N, Out], w:Witness.Aux[Out]): Out
    = w.value
  </code></pre>
  
  <p>Scala tells me that it can't summon a <code>Witness</code> 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 <code>Witness</code> won't work since there is only a single inhabitant for a class like <code>_7</code>.</p>
  
  <p>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 <code>Out</code> directly from <code>apply</code>.</p>
  
  <p>I think a possible solution might leverage implicit macros.</p>
  
  <p>Any and all ideas are welcome. I encourage you to leave a note if the question isn't clear.</p>