Благодаря ответу @MilesSabin я могу написать последовательность Фибоначчи уровня типа:
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]]
То, что я действительно хотел бы сделать, это получить Witness
для Dense
и использовать его как:
def apply[Out <: Dense](n: Dense)(implicit f:Fib[n.N, Out], w:Witness.Aux[Out]): Out
= w.value
Scala говорит мне, что не может вызвать экземпляр Witness
. Я предполагаю, что это связано с тем, что моя кодировка натуральных чисел на уровне типов представляет собой связанный список битов, а не одноэлементный тип. Я не могу понять, почему Witness
не работает, ведь для такого класса, как _7
, есть только один обитатель.
Я пытаюсь материализовать значение для типа, который имеет только одно возможное значение. Таким образом, я могу получить Out
напрямую от apply
.
Я думаю, что возможное решение может использовать неявные макросы.
Приветствуются любые идеи. Я призываю вас оставить записку, если вопрос не ясен.