Add BoolRing type class
TomasMikula opened this issue · 7 comments
This is a proposal to add type class for Boolean rings.
A Boolean ring is a ring that satisfies x times x = x for all x (i.e. every element is idempotent with respect to multiplication).
There isn't general consensus whether a Boolean ring assumes 1 (multiplicative identity). Some sources refer to Boolean ring as a Boolean algebra without identity. However, since algebra.ring.Ring has 1, it makes sense for BoolRing to include 1 as well. Adding a Boolean ring without 1 could be addressed as a separate issue, possibly calling it BoolRng.
The above property implies:
- Every Boolean ring is a commutative ring.
- Every element is its own additive inverse, i.e.
x plus x = 0.
As a consequence of 1., BoolRing should extend algebra.ring.CommutativeRing.
As a consequence of 2., BoolRing can implement negate to be
def negate(x: A): A = xA Boolean ring is equivalent to a Boolean algebra, with conversions both ways.
Bool#asCommutativeRing already returns a Boolean ring. However, this fact is currently not captured by the return type.
Should we also have a method .asBooleanAlgebra or should this also subclass Bool?
I slightly prefer .asBooleanAlgebra, since it avoids possible ambiguities between a Bool[A] and its corresponding BoolRing[A] (and also so that Bool[A].asCommutativeRing.asBooleanAlgebra eq Bool[A].
But if you all prefer subclassing I think that would be OK here as well.
For a subclassing solution, it would be sufficient for Bool to extend CommutativeRing—no BoolRing needed. That was my original suggestion. Then @non pointed out that it could conflict with other, more natural implicit rings for the same type.
I will also note that if/when we add the versions without identity (i.e. a Boolean ring without identity, equivalent to a Boolean algebra without identity and relative complement instead of (absolute) complement), whether they are going to be the same type class or two different type classes will have to copy this decision.
I'm fine with either solution.
I tend to agree with @non that subclassing can be difficult when combined with implicit resolution. We do it in some cases, not others, and I guess there is no avoiding the judgement call.
If we did the subclassing route, you could make some wrapper class, case class BoolInt(toInt: Int) and define Bool[BoolInt] to remove the ambiguity, but this adds boxing costs that I don't see how to remove (insert discussion about zero cost type aliases that give compile errors when misused).
That said, I think the .as... approach with the law that it unwraps y.asX.asY eq y is a good approach.
Yeah, I don't think either design is better in all respects than the other, so I'm OK with taking that route. The type class instances are then free to implement both Bool and BoolRing by the same instance and have both asRing and asBool return this.
Hi, if no-one is working on this yet, I can try to put together a pull request.
Go for it! 😄