Separate exact and inexact division

Offen
  • Stimmt etwas nicht?
#294 0 Kommentare 1 Reaktion 0 zugewiesene Personen Auf GitHub ansehen

Dieses Issue hat noch niemand übernommen.

Bewertung

Schwierigkeit
5/5
Geschätzter Aufwand
Über eine Woche
Anfängerfreundlichkeit
25/100
Issue-Typ
Feature
Klarheit
Größtenteils klar
Aktivitätsstatus
Veraltet
Bereich
backend-api-design

Rechercherichtung

Start by reading the EuclideanRing and Field class definitions and the existing division, modulo, gcd, and lcm implementations and tests. The issue proposes changing class constraints and operator aliases, but leaves key behavior and compatibility decisions open. Done would require a settled design, updated instances and tests, and agreement on the breaking change.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

type: breaking change

This would be a pretty seismic breaking change, so I would not be at all surprised if we end up deciding to close this issue on this basis, but it comes up semi-frequently and I think it is at least worth considering and having a discussion to link to.

At the moment, we have just one division operator, div aka /, which is provided by the EuclideanRing class. This class also provides a mod operator:

class EuclideanRing a where
  div :: a -> a -> a
  mod :: a -> a -> a

The mod operator is required to be compatible with / in the sense that a = (a / b) * b + a `mod` b. This means that for types that support exact division, such as Rational and Number, we are required to set mod _ _ = 0. In a theoretical sense this is fine: every field is a Euclidean ring, and all of the laws are satisfied. Practically, however, this can be a bit of a footgun:

  • PureScript beginners often expect Prelude.mod to behave the same way as the % operator in JS and other languages, so that e.g. 5.0 `mod` 2.0 = 1.0 and 8.0 `mod` 3.0 = 2.0. In my view, it is almost always a mistake to use mod with a type that is a Field.
  • Functions like lcm and gcd which make use of mod internally are likely to produce unexpected results when used with types that have Field instances. For example, lcm = const and gcd = flip const for any type that has a Field instance. It's probably almost always an error to use lcm or gcd with types that have Field instances.

If something is probably almost always an error, it suggests that we should be leaning on the compiler to let us know when we are doing it. My proposal is that we define a new division operator to separate inexact/integer division from exact division, as follows:

  • Add exactDiv :: a -> a -> a to Field, with the requirement that exactDiv a b = a * recip b (provided that b is nonzero). The exactDiv function could be a member of Field or it could be a separate function with a Field constraint, but I think the former would be nice to allow people to supply more efficient implementations; division of floating point numbers is usually implemented in hardware, for example.
  • Weaken the superclass constraints on Field from (EuclideanRing a, DivisionRing a) to (CommutativeRing a, DivisionRing a)
  • Change the operator alias / to refer to exactDiv
  • Add a new operator alias // for EuclideanRing's div, which we could describe as "integer division".

After making these changes, we are free to separate the behaviour of mod from that of /. We can choose to either remove EuclideanRing instances for types like Number and Rational entirely, so that using mod on them is a type error, or we can choose to provide instances with a more Euclidean-ring-like behaviour. For example, we would be free to define mod on Number so that it does behave (more or less) the same way as JS's %; in this case we'd have to define // such that it always returns a integer, which is probably appropriate since we would be describing // as "integer division". For example we might have:

  • 4.5 // 1.25 = 3.0 - since 1.25 * 3.0 = 3.75
  • 4.5 `mod` 1.25 = 0.75 matching JS's %

which expresses that 1.25 goes into 4.5 three times, with 0.75 left over. Doing this would also allow lcm and gcd to behave more sensibly; with this instance, lcm and gcd would work the same way on integral Numbers as they would on Int. For fractional Numbers it'd still be a bit weird because of floating point inaccuracy, but for rationals we'd be able to have eg. lcm (1%2) (1%3) = 1%1.

This approach is partially inspired by what Python does: / is for exact division and // is for integer division. https://docs.python.org/3.1/tutorial/introduction.html#numbers

Vorherrschende Sprache
PureScript
Sterne
168
Forks
90
Ø Merge
3 T. 1 Std.
Gemergte PRs (30 T.)
1

Entwicklungsumgebung

  • Kein Dockerfile und keine Docker-Compose-Datei
  • Hat eine Pull-Request-Vorlage
  • Kein Beitragsleitfaden

Erste Schritte

  1. Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
  3. Forken Sie das Repository und arbeiten Sie in einem Branch.
  4. Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.

Mehr aus purescript/purescript-prelude

Alle Issues in purescript/purescript-prelude

Ähnliche Issues

Weitere Issues zu Backend & API Design

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.