Ord: Reflexivity law is wrong?

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

@JamieBallingall đang làm issue này rồi.

Từ ngày 18/10/2022.

  • #301 của @JamieBallingall — đang mở

Đánh giá

Độ khó
4/5
Thời gian dự kiến
3-5 ngày
Mức phù hợp với người mới
25/100
Loại issue
Lỗi
Độ rõ ràng
Khá rõ ràng
Mức độ hoạt động
Đình trệ
Lĩnh vực
backend

Hướng nghiên cứu

Read the Ord law documentation and the linked issue #174 and pull request #298 for context; pull request #301 is already open for this issue. The proposed change is to state reflexivity as “if a == b then a <= b”; determine whether that law is appropriate for Ord and how the example of unreduced rationals affects it before making a change.

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

Mô tả

A while back, after some discussion, we updated the antisymetry law of Ord from:

-- | - Antisymmetry: if `a <= b` and `b <= a` then `a = b`

to

-- | - Antisymmetry: if `a <= b` and `b <= a` then `a == b`

so as to connect Eq and Ord. See issue #174 and PR #298.

Ever since, the reflexivity law has been bugging me and I think we need to update that too. Currently, it reads

-- | - Reflexivity: `a <= a`

and I think it should read

-- | - Reflexivity: if `a == b` then `a <= b`

To explain why, I return to my old example of unreduced rational numbers. Take a rational number represented as a record with two fields (n and d) where d is not zero but without the requirement that n and d are coprime. We can define equality as

eq (Rat x) (Rat y) = x.n * y.d == y.n * x.d

But what if we then define Ord using dictionary order

compare (Rat x) (Rat y) = case compare x.n y.n of
  EQ -> compare x.d y.d
  neq -> neq

These two definitions satisfy the current laws, specifically Ord is reflexive, but:

> x = Rat {n: 2, d: 4}
> y = Rat {n: 1, d: 2}
> x == y
true

> x <= y
false

which is surely not what we want.

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.