Scala can be Boring and Absurd

Posted on May 26, 2020
ScalaProgrammingLiterate

I’ve written this blog post partially to try out some new Literate Scala tooling that I’m working on, but also as a test of a long running hypothesis of mine.

That in the same way that Haskell libraries provide a rich source of insipration for Scala libraries, most Haskell “Jokes” can be usefully ported into Scala.

As such, this article is pretty much a rehash of this Stack Overflow Anwser by Conor McBride and the Haskell package called Data.Boring that it inspired.

We’re going to start by defining a couple of type classes, the first one is called Boring. Lets make these sealed, i.e. closed for extention, since we want to set the rules about which types are Boring.

sealed trait Boring[A] {
  val boring: A
}

Having an instance for Boring[A] indicates that a type is Boring, it contains one possible value, which is also boring.

Lets also define another type class called Absurd:

sealed trait Absurd[A] {
  def absurd[X](a: A): X
}

An absurd type has zero possible values, if we stick to purely functional Scala (which, like a vampire, has no reflection) then it’s imposible for us to have a value which is absurd. As a result of this, if in any function, we have an absurd value, we can use it to do whatever we want. Quite literally: the absurd function lets us convert an absurd value into any other type, even types we know nothing about. This sits in stark contrast to Boring, if we have a Boring value, then there’s very little point doing anything with it, since it won’t tell us anything interesting.

Lets look at some instances to get a better feel for these typeclasses. We’ll take Absurd first.

First off, we need to define a type alias for the Empty type. In an ideal world, we’d be able to refer to this directly as Nothing. But unfortunately, due to a bug in the scala compiler, using Nothing directly leads to implicit resolution bugs.

As a work around, we can define Empty.T as an alias for subtypes of Nothing. Empty.T and Nothing are equivalent (we could write implicitly[Empty.T =:= Nothing]), but the scala compiler is slightly happier to work with Empty.T.

object Empty {
  type T <: Nothing
}
object Absurd extends LowerPriorityAbsurdImplicits {

When defining typeclasses, it’s convinient to use the apply method on the companion object to summon an instance.

  def apply[A: Absurd]: Absurd[A] = implicitly[Absurd[A]]

We can also add an implicit class for convinience; given an Absurd value a, this lets us call a.absurd[X] to create a value of any type X.

  implicit class AbsurdOps[A: Absurd](a: A){
    def absurd[X]: X = Absurd[A].absurd[X](a)
  }

In Scala, the empty type Nothing is a subtype of all other types. Nothing is Absurd. Since it’s empty, there are no possible values that a variable of type Nothing could take. # To define Absurd for nothing, we can take advantage of the fact that whatever type X is, Nothing will be a subtype of it. So we can simply return the value of type Nothing that’s passed in. The implementation of absurd for Nothing is just the identity function.

  implicit val absurdForEmptyT: Absurd[Empty.T] = new Absurd[Empty.T] {
    override def absurd[X](a: Empty.T): X = a
  }

If we have a type Either[A, B], and A and B are both absurd. Then it would be absurd for us to have a Left value, and it would be absurd for us to have a Right value. So, the entire Either must be absurd.

  implicit def absurdForEither[A: Absurd, B: Absurd]: Absurd[Either[A, B]] =
    new Absurd[Either[A, B]] { 
      override def absurd[X](e: Either[A, B]): X = e match {
        case Left(a)  => a.absurd[X]
        case Right(b) => b.absurd[X]
      }
    }

If we have a tuple of type (A, B), and either of the types A or B are absurd, then the Tuple is also absurd.

  implicit def absurdForLeftTuple[A: Absurd, B]: Absurd[(A, B)] = 
   new Absurd[(A, B)] { 
     override def absurd[X](t: (A, B)) = t._1.absurd[X]
   }
}

If we defined both of the tuple instances in the same scope. And we went looking for an Absurd instance for a tuple of two absurd types, then the compiler wouldn’t know which instance to pick. We’d get an implicit resolution error.

We can avoid this by moving the lower priority implicit into a separate trait. And having the original Absurd object inherit from it. The compiler will prioritize implicits defined in the Absurd object, to those defined in it’s parent traits.

trait LowerPriorityAbsurdImplicits {
 import Absurd._
 implicit def absurdForRightTuple[A, B: Absurd]: Absurd[(A, B)] =
    new Absurd[(A, B)] { 
      override def absurd[X](t: (A, B)): X = t._2.absurd[X]
    }
}

It’s possibly worth noticing that while Haskell’s Data.Boring has an instance for Absurd a => Absurd NonEmpty a. Scala doesn’t have a non-empty list type (outside of cats), so I haven’t bothered with this. Despite this, there’s an isomorphism between NonEmptyList[A] and (A, List[A]). And the absurdness of (for example) NonEmptyList[Empty.T] is evidenced by the existence of Absurd[(Empty.T, List[Empty.T])].

Now let’s add some instances for Boring

object Boring {

In the same way that we used Absurd.apply as shorthand for implicitly summoning an absurd instance, since the Boring typeclass consists of a single value. Lets go one step futher, and have Boring.apply return that value.

  def apply[A: Boring]: A = implicitly[Boring[A]].boring

Unlike Nothing, which couldn’t have a Absurd instance defined against it directly, requiring us to wrap it in Empty.T. We can define a perfectly acceptable Boring instance for Unit without jumping through any hoops.

  implicit def boringForUnit: Boring[Unit] = new Boring[Unit] {
    override val boring: Unit = ()
  }

If two types A and B are both boring, then a tuple (A, B) is also boring. There’s only one value that the tuple could take

  implicit def boringForTuple[A: Boring, B: Boring]: Boring[(A, B)] =
    new Boring[(A, B)] {
      override val boring: (A, B) = (Boring[A], Boring[B])
    }
Boring[(Unit, Unit)] == ((),())

If a type A is absurd, then it would be absurd for List[A] to contain any values. The only value that the list could take, would be List.empty. This would be boring.

  implicit def boringForList[A: Absurd]: Boring[List[A]] = new Boring[List[A]] {
    override val boring: List[A] = List.empty
  }
Boring[List[Nothing]] == List()

In the same way that having A be absurd implies that a List[A] is boring, it also implies that Option[A] would also be boring.

  implicit def boringForOption[A: Absurd]: Boring[Option[A]] =
    new Boring[Option[A]] {
      override val boring: Option[A] = None
    }
Boring[Option[Nothing]] == None

If one side of an Either is absurd, and the other is boring, then the whole Either is boring.

   implicit def boringForLeftEither[A: Boring, B: Absurd]: Boring[Either[A, B]] = 
    new Boring[Either[A, B]]{
      override val boring: Either[A,B] = Left(Boring[A])
    }
   implicit def boringForRightEither[A: Absurd, B: Boring]: Boring[Either[A, B]] = 
    new Boring[Either[A, B]]{
      override val boring: Either[A,B] = Right(Boring[B])
    }
Boring[Either[Unit, Empty.T]] == (Left(()))
Boring[Either[Empty.T, Unit]] == (Right(()))
}
object Erata {

It’s sometimes interesting to take type constructors, (like List[_]) and fill them in with something boring (like Unit), and see what information remains. For example, Option[Unit] is a version of Boolean:

  def optionToBoolean[B:Boring](o: Option[B]): Boolean = o match {
    case Some(_) => true
    case None => false
  }
  def booleanToOption[B:Boring](b: Boolean): Option[B] = if(b) { 
    Some(Boring[B])
   } else {
    None
   }  

Similarly List[Unit] is isomorphic to the natural numbers

    def listToInt[B: Boring](l: List[B]) = l.length
    def intToList[B: Boring](i: Int): List[B] = List.fill(i)(Boring[B])
}

In case the boring/absurd language has been too opaque, these typeclasses are really about cardinality. Every type has a cardinality: a (possibly infinite) count of the number of values that it may have.

The boring and absurd typeclasses model two of the more interesing possible cardinalities: one and zero. Every boring type has exacly one value, so knowing that value doesn’t tell us anything. Every absurd type has zero values, so if we do know that value, something’s gone wrong.

As mentioned above, this blog post is Literate Scala, view the raw sourcecode here.