Separate exact and inexact division

未关闭
  • 哪里不对？
#294 0 条评论 1 个 reaction 已指派 0 人 在 GitHub 查看

还没有人认领这个 Issue。

评估

难度
5/5
预计耗时
一周以上
新手友好度
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 小时
30 天内合并 PR
1

环境准备

  • 没有 Dockerfile 或 Docker Compose 文件
  • 有 Pull Request 模板
  • 没有贡献指南

从这里开始

  1. 先读完整个 Issue，再读项目的贡献指南。
  2. 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
  3. Fork 仓库，在一个分支上完成修改。
  4. 提交 Pull Request，并在描述里引用这个 Issue 编号。

purescript/purescript-prelude 的其他 Issue

查看 purescript/purescript-prelude 的全部 Issue

相似的 Issue

更多 Backend & API Design Issue

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。