Pattern matching is overrated! All we need is a catamorphism!

AdtEncodingsBench.scala

package scalaz

import org.openjdk.jmh.annotations._

@Fork(1)
@BenchmarkMode(Array(Mode.Throughput))
class AdtEncodingsBench {

  import AdtEncodingsBench._

  @Benchmark def patMatchMaybe = runMaybe(PatMatchMaybe.just(_))(PatMatchMaybe.empty, _.fold(_)(_), _.map(_))
  @Benchmark def dispatchMaybe = runMaybe(DispatchMaybe.just(_))(DispatchMaybe.empty, _.fold(_)(_), _.map(_))

  @Benchmark def patMatchEither = runEither(PatMatchEither.left[Int, Int](_))(PatMatchEither.right(_), _.fold(_)(_), _.map(_))
  @Benchmark def dispatchEither = runEither(DispatchEither.left[Int, Int](_))(DispatchEither.right(_), _.fold(_)(_), _.map(_))

  /*
  JMH show that the encodings are mostly equivalent perf-wise.
  But I think the fold encoding allow for more versatile usages (eg. lazy constructors).
  Also singleton values could be theoretically encoded without cast/Nothing if/when https://issues.scala-lang.org/browse/SI-9916 is solved.
   */


}
object AdtEncodingsBench {

  def runMaybe[F[_]](just: Int => F[Int])(empty: F[Int], fold: (F[Int], Int => Int, => Int) => Int, map: (F[Int], Int => Int) => F[Int]): Int =
    (1 to 10000).map(i => (if (i % 3 == 0) empty else just(i)))
      .map(m => map(m, _ + 1))
      .foldLeft(0)((b, a) => fold(a, identity[Int], -1) + b)

  def runEither[F[_, _]](left: Int => F[Int, Int])(right: Int => F[Int, Int], fold: (F[Int, Int], Int => Int, Int => Int) => Int, map: (F[Int, Int], Int => Int) => F[Int, Int]): Int =
    (1 to 10000).map(i => (if (i % 3 == 0) left(i) else right(i)))
      .map(m => map(m, _ + 1))
      .foldLeft(0)((b, a) => fold(a, identity[Int], identity[Int]) + b)
}


object PatMatchMaybe {

  case object Empty extends Maybe[Nothing]

  final case class Just[A](a: A) extends Maybe[A]

  sealed abstract class Maybe[A] {
    final def fold[B](f: A => B)(b: => B): B = this match {
      case Just(a) => f(a)
      case _ => b
    }

    final def map[B](f: A => B): Maybe[B] = fold(a => just(f(a)))(empty)
  }

  def empty[A]: Maybe[A] = Empty.asInstanceOf[Maybe[A]]

  def just[A](a: A): Maybe[A] = Just(a)
}


object DispatchMaybe {

  trait Maybe[A] {
    def fold[B](f: A => B)(b: => B): B
  }

  object Empty extends Maybe[Nothing] {
    override def fold[B](f: (Nothing) => B)(b: => B): B = b
  }

  final class Just[A](val a: A) extends Maybe[A] {
    override def fold[B](f: (A) => B)(b: => B): B = f(a)
  }

  final class Lazy[A](private[this] var eval: () => Maybe[A]) extends Maybe[A] {
    lazy val value: Maybe[A] = {
      val value0 = eval()
      eval = null
      value0
    }

    override def fold[B](f: (A) => B)(b: => B): B = value.fold(f)(b)
  }

  def empty[A]: Maybe[A] = Empty.asInstanceOf[Maybe[A]]

  def just[A](a: A): Maybe[A] = new Just(a)

  def Lazy[A](m: => Maybe[A]): Maybe[A] = new Lazy(() => m)

  implicit final class MaybeFunctions[A](val maybe: Maybe[A]) extends AnyVal {
    def map[B](f: A => B): Maybe[B] = maybe.fold(a => just(f(a)))(empty)
  }

}

object PatMatchEither {


  sealed abstract class Either[A, B] {
    final def fold[C](l: A => C)(r: B => C): C = this match {
      case Left(a)   => l(a)
      case Right(b)  => r(b)
    }

    final def map[C](f: B => C): Either[A, C] = fold(left[A, C])(b => right(f(b)))
  }

  final case class Left[A, B](a: A) extends Either[A, B]

  final case class Right[A, B](b: B) extends Either[A, B]

  def left[A, B](a: A): Either[A, B] = Left(a)
  def right[A, B](b: B): Either[A, B] = Right(b)
}

object DispatchEither {

  trait Either[A, B] {
    def fold[C](l: A => C)(r: B => C): C
  }

  final class Left[A, B](val a: A) extends Either[A, B] {
    override def fold[C](l: (A) => C)(r: (B) => C): C = l(a)
  }

  final class Right[A, B](val b: B) extends Either[A, B] {
    override def fold[C](l: (A) => C)(r: (B) => C): C = r(b)
  }

  def left[A, B](a: A): Either[A, B] = new Left(a)

  def right[A, B](b: B): Either[A, B] = new Right(b)


  implicit final class EitherFunctions[A, B](val e: Either[A, B]) extends AnyVal {
    def map[C](f: B => C): Either[A, C] = e.fold(left[A, C])(b => right(f(b)))
  }
}