Grenzen des Nat-Typs in Shapeless

151

In Shapeless stellt der Nat-Typ eine Möglichkeit dar, natürliche Zahlen auf Typebene zu codieren. Dies wird beispielsweise für Listen mit fester Größe verwendet. Sie können sogar Berechnungen auf Typebene durchführen, z. B. eine Liste von NElementen an eine Liste von KElementen anhängen und eine Liste zurückerhalten, von der zum Zeitpunkt der Kompilierung bekannt ist, dass sie N+KElemente enthält.

Kann diese Darstellung große Zahlen darstellen, z. B. 1000000oder 2 53 , oder wird der Scala-Compiler dadurch aufgeben?

scala numbers compiler-optimization shapeless Rüdiger Klaehn
quelle
21
Miles ' NE Scala-Präsentation im letzten Jahr befasst sich mit dieser Frage, und die kurze Antwort lautet, dass es möglich wäre, große Zahlen auf Typebene in Scala - oder zumindest in 2.10 - mit Singleton-Typen darzustellen , aber es lohnt sich möglicherweise nicht . Shapeless 2.0 verwendet derzeit noch die Church-Codierung, mit der Sie ungefähr 1.000 erreichen, bevor der Compiler aufgibt.
Travis Brown
3
Ich werde später heute versuchen, eine Antwort mit etwas mehr Kontext zu schreiben. Nebenbei bemerkt, es ist nicht allzu schwierig, mit ganzzahligen Singleton-Typen zu arbeiten, wenn Sie größere Nummern auf Textebene benötigen - siehe zum Beispiel meinen Blog-Beitrag hier oder die Singleton-Funktionalität in Shapeless .
Travis Brown
2
Wenn Sie mit großen Zahlen auf Textebene rechnen möchten, können Sie diese als verknüpfte Liste von Bits implementieren.
Karol S
1
@ KarolS Ich habe eine Umsetzung dieser Strategie! Und ich würde es gerne zu formlos beitragen, wenn jemand interessiert ist, obwohl es wertlos ist, es sei denn, jemand kann helfen, stackoverflow.com/questions/31768203/… zu
Beefyhalo
2
Es sieht so aus, als ob stackoverflow.com/questions/31768203/… gelöst ist. Können Sie also Ihren Code beisteuern und die Frage mit Ihrer eigenen Antwort schließen?
Andriy Kuba

Antworten:

17

Ich werde es selbst versuchen. Ich werde gerne eine bessere Antwort von Travis Brown oder Miles Sabin annehmen.

Nat kann derzeit nicht zur Darstellung großer Zahlen verwendet werden

In der aktuellen Implementierung von Nat entspricht der Wert der Anzahl der verschachtelten formlosen.Succ [] -Typen:

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

Um die Zahl 1000000 darzustellen, hätten Sie einen Typ, der 1000000 Ebenen tief verschachtelt ist, was den Scala-Compiler definitiv in die Luft jagen würde. Die aktuelle Grenze scheint beim Experimentieren bei etwa 400 zu liegen, aber für angemessene Kompilierungszeiten ist es wahrscheinlich am besten, unter 50 zu bleiben.

Es gibt jedoch eine Möglichkeit, große Ganzzahlen oder andere Werte auf Typebene zu codieren, vorausgesetzt, Sie möchten keine Berechnungen für sie durchführen . Soweit ich weiß, können Sie mit diesen nur überprüfen, ob sie gleich sind oder nicht. Siehe unten.

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

Dies könnte verwendet werden, um z. B. dieselbe Arraygröße zu erzwingen, wenn Bitoperationen für Array [Byte] ausgeführt werden.

Rüdiger Klaehn
quelle
Ich habe gerade diese Antwort gesehen und +1, das ist ein gutes Beispiel. Es ist erwähnenswert, aber , dass Sie könnte Typklassen wie zB Shapeless die bieten ops.nat.Sumdas würde bezeugen , dass zwei Typ-Level - Zahlen eine bestimmte Summe hatte usw. (sie würden nur durch ein Makro zur Verfügung gestellt werden müssen).
Travis Brown
1
Hier ist ein Beispiel für eine ConcatTypklasse, mit der zwei Zeichenfolgen auf Typebene über ein Makro verkettet werden können. Eine Typklasse zum Summieren von Ganzzahlen auf Typebene würde wahrscheinlich sehr ähnlich aussehen.
Frank S. Thomas
5

Shapeless Natcodiert natürliche Zahlen auf Textebene mithilfe der Church-Codierung. Eine alternative Methode besteht darin, die Naturtöne als HL-Liste von Bits auf Typebene darzustellen.

Schauen Sie sich dicht an, was diese Lösung in einem formlosen Stil implementiert.

Ich habe eine Weile nicht mehr daran gearbeitet, und es braucht Lazyhier und da eine Prise formloser Dinge, wenn Scalac aufgibt, aber das Konzept ist solide :)

Beefyhalo
quelle