Separate exact and inexact division

オープン
  • 何か問題がありますか？
#294 コメント 0 件 リアクション 1 件 担当者 0 名 GitHub で見る

まだ誰も着手していません。

評価

難易度
5/5
見積もり時間
1週間以上
初心者へのやさしさ
25/100
issue の種類
機能追加
明瞭さ
おおむね明確
活発さ
停滞
領域
backend-api-design

調査の方向性

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.

索引モデルが issue の本文から書いたものです。

説明

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

主要言語
PureScript
スター
168
フォーク
90
平均マージ
3日 1時間
マージ済み PR（30日）
1

環境構築

  • Dockerfile・Docker Compose ファイルなし
  • プルリクエストのテンプレートあり
  • コントリビューションガイドなし

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

purescript/purescript-prelude のほかの issue

purescript/purescript-prelude の issue をすべて見る

似ている issue

Backend & API Design の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。