Limites de type Nat dans Shapeless

151

En informe, le type Nat représente un moyen d'encoder des nombres naturels à un niveau de type. Ceci est utilisé par exemple pour les listes de taille fixe. Vous pouvez même faire des calculs au niveau du type, par exemple ajouter une liste d' Néléments à une liste d' Kéléments et récupérer une liste qui est connue au moment de la compilation pour avoir des N+Kéléments.

Cette représentation est-elle capable de représenter de grands nombres, par exemple 1000000ou 2 ⁵³ , ou est-ce que cela fera abandonner le compilateur Scala?

scala numbers compiler-optimization shapeless Rüdiger Klaehn
la source

La présentation NE Scala de Miles l' année dernière aborde cette question, et la réponse courte est qu'il serait possible de représenter de grands nombres au niveau du type dans Scala - ou du moins en 2.10 - en utilisant des types singleton , mais cela ne vaut peut-être pas la peine . Shapeless 2.0 utilise toujours l'encodage Church, qui vous amènera à environ 1000 avant que le compilateur n'abandonne.

Travis Brown

J'essaierai d'écrire une réponse avec un peu plus de contexte plus tard dans la journée. En remarque, il n'est pas trop difficile de travailler avec des types de singleton entiers si vous avez besoin de plus grands nombres de niveau de type - voir par exemple mon article de blog ici ou la fonctionnalité de singleton dans Shapeless .

Travis Brown

Si vous voulez faire de l'arithmétique sur de grands nombres de type type, vous pouvez envisager de les implémenter sous forme de liste chaînée de bits.

Karol S

@KarolS J'ai une mise en œuvre de cette stratégie! Et je serais heureux de contribuer à informe si quelqu'un est intéressé, même si cela ne vaut rien à moins que quelqu'un ne puisse aider à résoudre stackoverflow.com/questions/31768203

...

Il semble que stackoverflow.com/questions/31768203/… soit résolu, alors pouvez-vous contribuer à votre code et fermer la question avec votre propre réponse?

Andriy Kuba du

Réponses:

J'essaierai moi-même. J'accepterai volontiers une meilleure réponse de Travis Brown ou Miles Sabin.

Nat ne peut actuellement pas être utilisé pour représenter de grands nombres

Dans l'implémentation actuelle de Nat, la valeur correspond au nombre de types imbriqués sans forme.Succ []:

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

Donc, pour représenter le nombre 1000000, vous auriez un type imbriqué à 1000000 niveaux de profondeur, ce qui ferait certainement exploser le compilateur scala. La limite actuelle semble être d'environ 400 à partir de l'expérimentation, mais pour des temps de compilation raisonnables, il serait probablement préférable de rester en dessous de 50.

Cependant, il existe un moyen d'encoder de grands entiers ou d'autres valeurs au niveau du type, à condition que vous ne souhaitiez pas effectuer de calculs sur eux . La seule chose que vous pouvez faire avec ceux-ci pour autant que je sache, c'est de vérifier s'ils sont égaux ou non. Voir ci-dessous.

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

Cela pourrait être utilisé par exemple pour appliquer la même taille de tableau lors d'opérations sur les bits sur Array [Byte].

Rüdiger Klaehn
la source

Je viens de voir cette réponse, et +1, c'est un bon exemple. Il est intéressant de noter cependant que vous pouvez fournir des classes de types comme par exemple Shapeless's ops.nat.Sumqui témoigneraient que deux entiers au niveau du type avaient une somme particulière, etc. (ils devraient juste être fournis par une macro).

Travis Brown

Voici un exemple de Concatclasse de type qui permet de concaténer deux chaînes au niveau du type via une macro. Une classe de type pour la somme des entiers au niveau du type serait probablement très similaire.

Frank

Shapeless's Natencode les nombres naturels au niveau du type en utilisant l'encodage Church. Une autre méthode consiste à représenter les naturels comme une HList de niveau de type de bits.

Découvrez dense qui met en œuvre cette solution dans un style informe.

Je n'ai pas travaillé dessus depuis un moment, et il faut une pincée d'informe ' Lazyici et là pour quand scalac abandonne, mais le concept est solide :)

beefyhalo
la source