scala - plus - Límites del tipo Nat en Shapeless

nat estricta detectada

Question

En informe, el tipo Nat representa una forma de codificar números naturales en un nivel de tipo. Esto se usa, por ejemplo, para listas de tamaño fijo. Incluso puede hacer cálculos en el nivel de tipo, por ejemplo, agregar una lista de N elementos a una lista de elementos K y obtener una lista conocida en tiempo de compilación para tener elementos N+K

¿Es esta representación capaz de representar números grandes, por ejemplo, 1000000 o 2 ⁵³ , o esto causará que el compilador Scala se dé por vencido?

Answer 1

El Nat de Shapeless codifica números naturales en el nivel de tipo usando la codificación de la Iglesia. Un método alternativo es representar lo natural como un HList de bits de nivel de tipo.

Echa un vistazo a dense que implementa esta solución en un estilo sin forma.

No he trabajado en ello desde hace tiempo, y necesita una pizca de '' Lazy aquí y allá para cuando Scalac se da por vencido, pero el concepto es sólido :)

Answer 2

Voy a intentar uno yo mismo. Acepto gustosamente una mejor respuesta de Travis Brown o Miles Sabin.

Nat no se puede usar actualmente para representar números grandes

En la implementación actual de Nat, el valor corresponde a la cantidad de tipos anidados sin forma.Succ []:

scala> Nat(3)
res10: shapeless.Succ[shapeless.Succ[shapeless.Succ[shapeless._0]]] = Succ()

Entonces, para representar el número 1000000, tendría un tipo que está anidado a 1000000 niveles de profundidad, lo que definitivamente haría estallar el compilador scala. El límite actual parece ser de aproximadamente 400 por experimentación, pero por tiempos de compilación razonables, probablemente sería mejor permanecer debajo de 50.

Sin embargo, hay una forma de codificar enteros grandes u otros valores a nivel de tipo, siempre que no desee hacer cálculos sobre ellos . Lo único que puedes hacer con ellos hasta donde yo sé es comprobar si son iguales o no. Vea abajo.

scala> type OneMillion = Witness.`1000000`.T
defined type alias OneMillion

scala> type AlsoOneMillion = Witness.`1000000`.T
defined type alias AlsoOneMillion

scala> type OneMillionAndOne = Witness.`1000001`.T
defined type alias OneMillionAndOne

scala> implicitly[OneMillion =:= AlsoOneMillion]
res0: =:=[OneMillion,AlsoOneMillion] = <function1>

scala> implicitly[OneMillion =:= OneMillionAndOne]
<console>:16: error: Cannot prove that OneMillion =:= OneMillionAndOne.
       implicitly[OneMillion =:= OneMillionAndOne]
                 ^

Esto podría usarse para, por ejemplo, aplicar el mismo tamaño de matriz al realizar operaciones de bits en Array [Byte].