Separate exact and inexact division

Đang mở
  • Có gì không ổn?
#294 0 bình luận 1 reaction 0 người được giao Xem trên GitHub

Chưa có ai nhận issue này.

Đánh giá

Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức phù hợp với người mới
25/100
Loại issue
Tính năng
Độ rõ ràng
Khá rõ ràng
Mức độ hoạt động
Đình trệ
Lĩnh vực
backend-api-design

Hướng nghiên cứu

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.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

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

Ngôn ngữ chính
PureScript
Star
168
Fork
90
Merge trung bình
3 ngày 1 giờ
Pull request đã merge (30 ngày)
1

Chuẩn bị môi trường

  • Không có Dockerfile hay tệp Docker Compose
  • Có mẫu pull request
  • Không có hướng dẫn đóng góp

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của purescript/purescript-prelude

Tất cả issue của purescript/purescript-prelude

Issue tương tự

Thêm issue về Backend & API Design

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.