Limites do tipo Nat em informe

151

Sem forma, o tipo Nat representa uma maneira de codificar números naturais em um nível de tipo. Isso é usado, por exemplo, para listas de tamanho fixo. Você pode até fazer cálculos no nível de tipo, por exemplo, anexar uma lista de Nelementos a uma lista de Kelementos e recuperar uma lista que é conhecida em tempo de compilação por ter N+Kelementos.

Essa representação é capaz de representar grandes números, por exemplo, 1000000ou 2 53 , ou isso fará com que o compilador Scala desista?

scala numbers compiler-optimization shapeless Rüdiger Klaehn
fonte
21
A apresentação do NE Scala de Miles no ano passado trata dessa questão, e a resposta curta é que seria possível representar grandes números no nível de tipo no Scala - ou pelo menos no 2.10 - usando tipos singleton , mas pode não valer a pena . Atualmente, o Shapeless 2.0 ainda usa a codificação da Igreja, que o leva a mais ou menos 1.000 antes que o compilador desista.
Travis Brown
3
Vou tentar escrever uma resposta com um pouco mais de contexto ainda hoje. Como uma observação lateral, não é muito difícil trabalhar com tipos inteiros de singleton se você precisar de números maiores de nível de tipo - veja, por exemplo, minha postagem no blog aqui ou a funcionalidade singleton em Shapeless .
Travis Brown
2
Se você deseja fazer aritmética em números grandes de nível de tipo, considere implementá-los como uma lista vinculada de bits.
Karol S
1
@KarolS Eu tenho uma implementação dessa estratégia! E eu ficaria feliz em contribuir para disforme se alguém estiver interessado, embora seja inútil a menos que alguém pode ajudar a resolver stackoverflow.com/questions/31768203/...
beefyhalo
2
Parece que o stackoverflow.com/questions/31768203/… está resolvido, então você pode contribuir com seu código e fechar a pergunta com sua própria resposta?
Andriy Kuba

Respostas:

17

Vou tentar um eu mesmo. Terei prazer em aceitar uma resposta melhor de Travis Brown ou Miles Sabin.

O Nat atualmente não pode ser usado para representar grandes números

Na implementação atual do Nat, o valor corresponde ao número de tipos aninhados sem forma.Succ []:

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

Portanto, para representar o número 1000000, você teria um tipo aninhado em 1000000 níveis de profundidade, o que definitivamente explodiria o compilador scala. O limite atual parece ser cerca de 400 da experimentação, mas por tempos razoáveis ​​de compilação provavelmente seria melhor ficar abaixo de 50.

No entanto, existe uma maneira de codificar números inteiros grandes ou outros valores no nível do tipo, desde que você não queira fazer cálculos sobre eles . A única coisa que você pode fazer com as pessoas que eu saiba é verificar se elas são iguais ou não. Ver abaixo.

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

Isso pode ser usado para, por exemplo, impor o mesmo tamanho de matriz ao realizar operações de bits na matriz [Byte].

Rüdiger Klaehn
fonte
Acabei de ver esta resposta e +1, este é um bom exemplo. Vale a pena notar, no entanto, que você poderia fornecer classes de tipos como, por exemplo, Shapeless, ops.nat.Sumque testemunhariam que dois números inteiros no nível de tipo tinham uma soma específica etc. (eles apenas precisariam ser fornecidos por uma macro).
Travis Brown
1
Aqui está um exemplo de uma Concatclasse de tipo que permite concatenar duas seqüências de caracteres de nível de tipo por meio de uma macro. Uma classe de tipo para somar números inteiros em nível de tipo provavelmente seria muito semelhante.
31416 Frank S. Thomas
5

O Shapeless's Natcodifica números naturais no nível do tipo usando a codificação da Igreja. Um método alternativo é representar os naturais como uma lista de bits de nível de tipo.

Confira denso que implementa esta solução em um estilo disforme.

Eu não trabalho nisso há um tempo, e ele precisa de uma pitada de disforme ' Lazyaqui e ali para quando o scalac desistir, mas o conceito é sólido :)

beefyhalo
fonte