Separate exact and inexact division

Aperta
  • Qualcosa non va?
#294 0 commenti 1 reazione 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
25/100
Tipo di issue
Funzionalità
Chiarezza
Abbastanza chiara
Stato di attività
Ferma
Ambito
backend-api-design

Direzione di ricerca

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.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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

Lingua principale
PureScript
Stelle
168
Fork
90
Merge medio
3g 1h
PR unite (30g)
1

Preparare l'ambiente

  • Nessun Dockerfile né file Docker Compose
  • Ha un modello di pull request
  • Nessuna guida per i contributori

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di purescript/purescript-prelude

Tutte le issue di purescript/purescript-prelude

Issue simili

Altre issue su Backend & API Design

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.