Enumerable (WIP)

[isomarcte]

Prototyping adding the Enumerable class to cats. This class is based on https://hackage.haskell.org/package/base-4.15.0.0/docs/GHC-Enum.html#v:toEnum but tries to avoid some pitfalls that the Haskell version has (e.g. toEnum doesn't throw in our version) and relates to the other classes currently defined in Enumerable.scala.

This isn't remotely complete, but I thought I'd start a PR so we can have a central place to discuss the work as it progresses.

Open Questions

• How should all of these classes related to each other?
• Do we need a few more classes? @satorg talked about a CycleNext class for example in #4347.
• What laws (if any) should this (these) classes have?
• Should cycleNext or cyclePrevious for types which have Next or Previous be defined as aliases for next and previous?

Update, Current State And Proposed Changes

I've been hacking these classes for a bit now and I think I've got a more concrete proposal about how they should line up, as well as some questions I'd like to raise to a broader audience. There's a lot going on here, so I apologize in advance for the upcoming wall of text.

In the class hierarchy diagrams below, I'm only showing the abstract methods on the class.

Current Hierarchy

This is the current class hierarchy. There are a few things worth pointing out that are suspect.

1. PartialNext, PartialPrevious, UpperBounded and LowerBounded compose in PartialOrder, rather than extending it. The situation is similar for BoundedEnumerable and UnboundedEnumerable with respect to Order.
2. PartialNextLowerBounded and PartialPreviousUpperBounded have no abstract members. BoundedEnumerable and UnboundedEnumerable only have Order as an abstract member.
3. PartialNextLowerBounded extends PartialNext, LowerBounded, and PartialPrevious
4. PartialPreviousUpperBounded extends PartialPrevious, UpperBounded, and PartialNext

TL;DR The current hierarchy encourages the use of incoherent instances for some behaviors, inconsistently uses certain patterns to defend against invalid behavior in the presence of incoherent instances, and has some naming issues.

Something to note is that many of these classes have a def reverse function which reverses the ordering, which we will dicuss a bit below.

Composing PartialOrder and Order

I don't know why we are composing in PartialOrder and Order as an abstract member on these classes, rather than extending it. As a side effect of the reverse function, composing the class as a member rather than extending it means that a function like this might lead to incorrect behaviors that are difficult to detect.

// Dangerous because the ordering used to compare values is not the same as the ordering used by PartialNext
def nextIfMin[A: PartialOrder: PartialNext](x: A, y: A): Option[A] = if (x < y) PartialNext.partialNext(x) else Some(x)

There are two possible ways to make this better that come to mind.

• PartialNext extends PartialOrder (yes I know this isn't bincompat, we'll come back to that)
• Discourage and deprecate reverse in favor of something like Inverse.

We could do either or both of these. They are not mutually exclusive.

PartialNextLowerBounded and PartialPreviousUpperBounded

With respect to PartialNextLowerBounded and PartialPreviousUpperBounded not having any abstract members, this seems very odd to me. I expect a typeclass to introduce some abstract behavior that is then used to provide some new functionality, rather than just composing multiple already defined classes. These classes do have a non-abstract members, for example def membersDescending: Stream[A]. The reason for this encoding seems to be because membersDescending needs to access the UpperBounded.maxBound. One could define membersDescending on PartialPrevious like so,

  def membersDescending(implicit A: UpperBounded[A]): Stream[A]

This is consistent with how we define methods on other classes, for example isEmpty on Monoid demands an Eq[A] constraint. For example, we don't introduce a class like trait EqMonoid[A] extends Monoid[A] with Eq[A] just to define the method isEmpty.

It seems the reason we don't define membersDescending with an implicit constraint is so that in the event of a reverse we can ensure we are using the correct constraint. For example, if membersDescending was defined with a constraint and someone reverses a BoundedEnumerable then they would likely get the wrong UpperBounded when calling the membersDescending on the reversed BoundedEnumerable. Although, it may not have been as intentional as that. The PR which added them doesn't seem to discuss any of this..

An alternative way we could resolve this is by discouraging the use of incoherent instances and encouraging the use of newtypes such as Inverse.

Also, as a small aside, the names seem wrong. These classes extend from both PartialNext and PartialPrevious, but they are named as though they only extend from one.

Proposed New Hierarchy

Here is my ideal proposed new hierarchy.

Major differences

• We don't compose PartialOrder and Order as members on the classes, we extend them.
• A new Enumerable class is added between PartialNext/PartialPrevious and UnboundedEnumerable/BoundableEnumerable.
• Every class defines at least one abstract method.

Although I elided them in this graphic, there are a great many useful concrete methods one can define on these classes. Some require related constraints, for example PartialNext could have this method.

trait PartialNext[A] extends PartialOrder[A] {
  def nextOrMinBy(a: A, n: BigInt)(implicit A: LowerBounded[A]): A = {
    val Zero: BigInt = BigInt(0)
    val One: BigInt =  BigInt(1)

    @tailrec
    def loop(acc: A, n: BigInt): A =
      if (n <= Zero) {
        acc
      } else {
        partialNext(acc) match {
          case Some(acc) =>
            loop(acc, n - One)
          case _ =>
            loop(A.minBound, n - One)
        }
      }

    loop(a, n)
  }
}

Bincompat

This would create bincompat issues. So it would either need to wait for cats 3.x.x or we'd have find some alternative names here and introduce a new hierarchy. I'm personally a slight fan latter, as I like to avoid bincompat breaks as long as possible.

Here are some ideas. Though, FWIW, I don't like them as much as the names we are currently using.

PartialNext -> PartialForward PartialPrevious -> PartialBackward Next -> Forward Previous -> Backward BoundedEnumerable -> BoundableEnumerable UnboundedEnumerable -> UnboundableEnumerable LowerBounded -> MinBounded UpperBounded -> MaxBounded

Enumerable is a net new class, so that can stay the same. Some classes in the current hierarchy would just be deprecated without a new class as their methods can be rolled into the other classes with constraints.

Alternative Updated Hierarchy

As an alternative, we could continue the current patterns. Have PartialOrder and Order be members on classes, and introduce new classes with no abstract methods in order to define utility functions like nextOrMinBy and membersDescending without using constraints.

Here is what that might look like with the addition of the Enumerable class.

In my opinion, that's quite messy.

The ergonomics of using this hierarchy are pretty bad as well. For example, if I need to write a function which uses nextOrMinBy and fromEnum, in this hierarchy defined on PartialNextLowerBounded and Enumberable respectively, and also a comparison, then I need this signature.

def foo[A: PartialNextLowerBounded: Enumberable: Order]

In this case, PartialNextLowerBounded provides a PartialOrder as a member (defined in both LowerBounded and PartialNext. Enumerable provides it's own, possibly completely different, Order as a member, and I also have the implicit Order in scope.

Thoughts?

[isomarcte]

cc @armanbilge @satorg

[isomarcte]

cc @zarthross

[isomarcte]

Should Next imply Order? Should it be true that a < next(a) for all A? Currently Next only implies PartialOrder.

[isomarcte]

Should cycleNext always include all elements at least once?

[satorg]

I am not sure about bringing BigInt into this hierarchy... It would be especially weird to see BigInt when we're working with some relatively simple type like Short.

[isomarcte]

@satorg yeah, I admit it is a little strange. We need something which maps to the natural numbers here, and the integer numbers (as in from negative infinity to positive infinity) is such a set, BigInt being the only sort of reasonable analog in scope.

In other words, we can't write a lawful instance of Enumerable for BigInt, unless we have a type which is at least as mappable to the natural numbers as BigInt is.

I'm open to other ideas here, I just can't think of anything.

[isomarcte]

@armanbilge @satorg I've updated the first post on this issues with an unreasonably long discussion on where we can go here. Let me know your thoughts (I don't expect any responses in the immediately :wink: )

[armanbilge]

I don't know why we are composing in PartialOrder and Order as an abstract member on these classes, rather than extending it.

This pattern is generally used to avoid ambiguous implicits. This is the same reason that FunctorFilter does not extend Functor. Further reading: https://typelevel.org/blog/2016/09/30/subtype-typeclasses.html

[isomarcte]

@armanbilge ah, that makes sense (and is unfortunate). I think my general proposal still stands, just with the branching class super types being members rather than extending them.

Do you guys have thoughts on it?

[isomarcte]

Actually, let me take another deeper look at this before we proceed. I'm not satisfied with the ergonomics of the solution I proposed, if we have to encode the super classes as members for each branching parent class. It may be an unsolvable problem without coherence built into the language, but I'd like to see if something else comes to mind.