Code review: cats-kernel

[denisrosset]

Hi all,

as algebra, and by extension spire both depend on cats-kernel, I quickly went through the cats-kernel package. Please find my observations below.

There are a few small inconsistencies that could be corrected before freezing binary compatibility. I also think that, while typeclasses and data types are documented, the motivation for the default instances is sometimes missing.

I'm not asking to correct any of those; I just want to be sure that we commit to the (sometimes implicit) choices we are making for the future.

Denis

Typeclasses

Hierarchy

• Two tails in the hierarchy Eq->Hash and Eq->PartialOrder->Order, could lead to ambiguous implicits (Ambiguous implicits when requesting Eq when both Hash and Order are present #2012)

Properties

• SemigroupFunctions.isCommutative/isIdempotent: document that a return value of true=property is valid, false=property may be not valid (as it uses internally isInstanceOf).

Alternative 1: rename as knownCommutative, or provenCommutative (as to understand that no does not mean violation of the property)

Suggestion: put the functions directly on the typeclass instance, and override def = true in the respective Band and CommutativeSemigroup traits

• maybeCombine are helper methods on the companion; in general, when should methods be part of the typeclass, when should they be part of the companion functions?

Exhaustiveness

We do not have magmas (i.e. non associative semigroups), nor quasigroups/loops (which are in scalaz 8 roadmap).

See: types of magma, https://en.wikipedia.org/wiki/Magma_(algebra)

We distinguish bands and semilattices, which are important for algebird/for the meet&join lattices in algebra.

Other classes of semigroups:

https://en.wikipedia.org/wiki/Special_classes_of_semigroups

Conversion methods

They would behave better on the companion object, which avoids syntax ambiguities when an instance inherits from several typeclasses.

• Semilattice.as[Meet|Join]PartialOrder

• Order.toOrdering, but no PartialOrder.toPartialOrdering

Automatic conversion to/from Scala instances

• Do we want the implicit conversions (Order->Ordering, PartialOrder->PartialOrdering) to be always available? In Spire, a special import is needed for them to be available.

Exhaustivity of methods

• Lack of exhaustivity: Ordering->Order conversion is available, but not PartialOrdering->PartialOrder (and no Hash->Hashing)

• No Eq.from and Hash.from, while PartialOrder.from and Order.from are available

Instances

• We do not distinguish between additive and multiplicative monoids/groups. Should we have default additive group instances for BigDecimal/BigInt/Byte/Double/Duration/Float/Int/Long/Short ? What will we do if algebra is merged into cats in the future?

• The BitSet semilattice is by default a bounded semilattice with the "or" operation. The "and" semilattice is also well defined, but is not bounded (as the BitSet of all numbers cannot probably be represented in memory). This has an impact on the partial order as well (but the partial order of inclusion makes probably more sense).

• Monoid[Either] is right biased, and this choice has probably implications on the choice of order/partial order. The choice is not motivated yet by laws.

• Function instances are defined by applying the operation on f(a). The semigroup of functions f: A => A under composition is not considered.

• The order/partial order for sequences (List, Queue, Stream, Vector) is not the (co)lexicographic order. It should be documented (could not find the name).

• The map monoid makes the following choice: set union for the keys, monoid combine for the values (extending the given semigroup to the monoid by adjunction of an identity, as a placeholder for missing values)

• Option order/partial order, what is the position of None (probably "-infinity")?

• The Set.eqv override does not override the original method as it is missing an implicit parameter.

• Order[String] is comparison by Unicode values of characters (JVM String.compareTo). Is it equivalent to the lexicographic comparison of String, considered as Vector[Char]?

Laws

• SerializableLaws returns a ScalaCheck object; wasn't the intent to relegate dependencies to the discipline package?

• GroupLaws, missing test for combineN and negative integers

• PartialOrderLaws, missing test for compatibility of partialComparison and tryCompare results with other methods

• OrderLaws, missing test for compatibility of comparison results with other methods

• What are the binary compatibility guidelines for kernel-laws? At some stage we may discuss the law encoding, see WIP: Switch laws to cats-core encoding algebra#206 (especially if algebra is moved to cats)

[kailuowang]

@johnynek , would you be interested in working with @denisrosset prioritizing the desired changes of Cats-kernel before 1.0 from Algebra/Spire/Algebird's perspective?

[johnynek]

@denisrosset Thanks for thinking about all these things. I'm happy to talk through some of these things.

What is the best way to reply? In most cases there are answers. In many cases these questions were brought up during review. In some cases I think you can answer the question perhaps at the repl (I believe UTF-8 was designed to have the same ordering as a byte-wise ordering (and thus, char-wise) ordering gives you. Also I believe the List ordering is lexicographic. Why do you say it is not? The A => A algebras have been discussed as defining an Endo[A] type, and @kailuowang recently added such a type alias, I'm -1 on magma since I can't imagine any use, and there is no law just the type signature).

I would prefer us minimize binary incompatibility since algebird depends on cats-kernel, and changes to anything touching semigroup or anything that extends it will create pains for people that use algebird and cats. If there are serious issues, of course we should consider.

Perhaps we can move this discussion to a google doc so we can more easily comment and discuss?

[denisrosset]

@johnynek Yes, let's move to a Google Doc. Here is it:

https://docs.google.com/document/d/1qTkUoBzEEL1yQ2GbJkJ0HwzymhjzcChojEVHmwfEoSs/edit?usp=sharing

Most (all?) of these remarks can be addressed by adding documentation. To not waste time, I will add comments in the code based on our discussions.

[kailuowang]

I submitted #2116. Is there any other items that are potentially binary breaking and thus blocking RC2 release ?

[ryanstull]

Not sure if this issue should still be open since cats 1.0.0 was released. I just added #2197 for adding Magma to the kernel, it still probably needs a bit of work though, and it might be worth it to add Quasigroup and Loop too if we decide to add this.