Design advice for lifted `Ordering`

Question
1

Hi, I’m in a bit of a design pickle…

I’ve got a lifted ordered type, Unbounded[X] that extends an existing choice of X with some ordering to become an extended type with additional negative-infinity and positive infinity values.

This has been around for a good few years, starting off in F#, then in Scala 2.10 and changing on the way into a Scala 2.13 form. It isn’t beautiful in its current form.

I’m trying to scratch a couple of itches and get it looking like the original F# form. This lets me treat the two infinity values as being shared across the various type instantiations of Unbounded[X] as common polymorphic values. That way, I can write:

Finite(2) > NegativeInfinity // No need for extra parentheses or type annotations.
NegativeInfinity < PositiveInfinity // No need for extra parentheses or type annotations.

There has been some back-and-forth on the design, but currently I’m going down the route used by Option[X], making the X a covariant type parameter and using case objects for the infinities. There is an impedance mismatch with the Ordering constraint on X, but I’ve fudged around this.

(I’ve also tried stuff along the lines of this snippet: use of custom unapply breaks exhaustivity checking · Issue #10660 · scala/bug · GitHub, but this didn’t play well with the parameterless patterns used to match the infinite values, so I’ve bounced back off that now).

What I’ve got now is this:

package com.sageserpent.americium

object Unbounded {
  implicit def ordering[X: Ordering]: Ordering[Unbounded[X]] =
    (first: Unbounded[X], second: Unbounded[X]) =>
      (first, second) match {
        case (Finite(thisUnlifted), Finite(anotherUnlifted)) =>
          Ordering[X].compare(thisUnlifted, anotherUnlifted)
        case (PositiveInfinity, PositiveInfinity) => 0
        case (NegativeInfinity, NegativeInfinity) => 0
        case (_, PositiveInfinity)                => -1
        case (NegativeInfinity, _)                => -1
        case (PositiveInfinity, _)                => 1
        case (_, NegativeInfinity)                => 1
      }

  implicit val negativeInfinityOrdering: Ordering[NegativeInfinity.type] =
    (one: NegativeInfinity.type, andTheSame: NegativeInfinity.type) => 0
  implicit val positiveInfinityOrdering: Ordering[PositiveInfinity.type] =
    (one: PositiveInfinity.type, andTheSame: PositiveInfinity.type) => 0

  implicit def finiteOrdering[X: Ordering]: Ordering[Finite[X]] =
    (first: Finite[X], second: Finite[X]) =>
      Ordering[X].compare(first.unlifted, second.unlifted)
}

sealed trait Unbounded[+X]

case class Finite[X: Ordering](unlifted: X) extends Unbounded[X]

case object NegativeInfinity extends Unbounded[Nothing]

case object PositiveInfinity extends Unbounded[Nothing]

So far so good. Now comes a rather pesky test:

import scala.math.Ordered.orderingToOrdered

// ....

  @TestFactory
  def negativeInfinityShouldBeLessThanAllFiniteValues(): DynamicTests =
    integerTrials
      .withLimit(100)
      .dynamicTests { underlying =>
        // First, via `Ordering`...
        assert(
          Ordering[Unbounded[Int]].lt(NegativeInfinity, Finite(underlying))
        ) // No bother at all.
        assert(
          Ordering[Unbounded[Int]].gt(Finite(underlying), NegativeInfinity)
        ) // Plain sailing.

        // Second, via `Ordered` as a syntax enhancement...
        assert(
          NegativeInfinity < Finite(underlying)
        ) // Compilation error - but maybe this is to be desired, given they are sibling types. It looks unintuitive, though.
        assert(
          NegativeInfinity < (Finite(underlying): Unbounded[Int])
        ) // Compilation error. This time it feels genuinely inconvenient.
        assert(
          (NegativeInfinity: Unbounded[Int]) < Finite(underlying)
        ) // No problem here.
        assert(
          Finite(underlying) > NegativeInfinity
        ) // Compilation error - but maybe this is to be desired, given they are sibling types. It looks unintuitive, though.
        assert(
          Finite(underlying) > (NegativeInfinity: Unbounded[Int])
        ) // Compilation error. This time it feels genuinely inconvenient.
        assert(
          (Finite(underlying): Unbounded[Int]) > NegativeInfinity
        )  // No problem here.
      }

So I’ve got the nice parameterless references to the infinities for both value references and patterns, but I’m getting caught out by the lack of covariance on Ordering, which is what drives the syntax enhancement via Ordered (courtesy of Ordered.orderingToOrdered). Ordered is also invariant on its type parameter. Or so I believe…

My current thinking is to try hacking in some variant of Ordered.orderingToOrdered to bridge the gap between the two infinities and the finite values. Or perhaps some kind of implicit conversion between the infinite value orderings and Ordering[Unbounded[X]].

Curious as to your thoughts…

(Also, if there’s already something out there doing this, do let me know. I’m more than happy to use the fruits of others’ labour.)

2

Musing, but would using an enum in Scala 3 help here?

The code is intended for mixed Scala 2.13 / 3 use, but going to Scala 3 only should not be ruled out…

3

Well, I tried my own suggestions, and they didn’t work. However, I was led to the following idea…

(If you are of a sensitive disposition, please look away now or read something about Haskell).

package com.sageserpent.americium

object Unbounded {
  implicit def ordering[X: Ordering]: Ordering[Unbounded[X]] =
    (first: Unbounded[X], second: Unbounded[X]) =>
      (first, second) match {
        case (Finite(thisUnlifted), Finite(anotherUnlifted)) =>
          Ordering[X].compare(thisUnlifted, anotherUnlifted)
        case (PositiveInfinity, PositiveInfinity) => 0
        case (NegativeInfinity, NegativeInfinity) => 0
        case (_, PositiveInfinity)                => -1
        case (NegativeInfinity, _)                => -1
        case (PositiveInfinity, _)                => 1
        case (_, NegativeInfinity)                => 1
      }
}

sealed trait Unbounded[+X]

case class Finite[X: Ordering](unlifted: X)
    extends Unbounded[X]
    with Ordered[Unbounded[X]] {
  override def compare(that: Unbounded[X]): Int =
    Unbounded.ordering.compare(this, that)
}

case object NegativeInfinity
    extends Unbounded[Nothing]
    with Ordered[Unbounded[_ <: Any]] {

  override def compare(that: Unbounded[_]): Int = that match {
    case NegativeInfinity => 0
    case _                => -1
  }
}

case object PositiveInfinity
    extends Unbounded[Nothing]
    with Ordered[Unbounded[_ <: Any]] {
  override def compare(that: Unbounded[_]): Int = that match {
    case PositiveInfinity => 0
    case _                => 1
  }
}

This means that NegativeInfinity and PositiveInfinity are now so utterly detached from any specific ordering semantics in the X of Unbounded[X] that they can even be ordered before or after values of X that have no ordering semantics, but I feel that is a good honest engineering wart I can live with. :grin:

If anyone knows a way of sneaking the Ordering constraint into the wildcards, do let me know…