GADTs_For_Implicits_Demo.scala

object Test {


/** Simple definition of Heterogeneous Lists
  */
sealed abstract class HList {
  def :::[H](head: H): H ::: this.type = Test.:::(head, this)
}

/** The empty list
  * It is defined as a class and not an object to simplfy typing
  */
final case class HNil()
  extends HList

/** Consing, prepend an element (of type H)
  * to the list (of type T)
  */
final case class :::[+H, +T <: HList](
    head: H,
    tail: T)
  extends HList


/** A small helper to log what the ordering is doing */
implicit final class OrderingOps[A](val self: Ordering[A]) {
  def log: Ordering[A] =
    new Ordering[A] {
      def compare(x: A, y: A): Int = {
        val r = self.compare(x,y)
        val op =
          if (r == 0) "=="
          else if (r < 0) "<"
          else ">"
        println(s"$x $op $y")
        r
      }
    }
}

/* We want to derive orderings for HList, both
   with left-to-right lexicographic ordering
   and  right-to-left ordering

   Lexicographic ordering is an ordering on tuples where
      (xa, xb) < (ya, yb)
      if and only if
      (xa < ya) or ( (xa == ya) and (xb < yb) )
*/

/* The first approach is the classical one defining
   a type-class (i.e. OrderingOfHList) and implicits
   for each use case.
*/
object FirstTry {

  /** The type class, with both left-to-right
    * and right-to-left ordering.
    * Note that adding a new way to order required
    * to modify the type-class.
    */
  trait OrderingOfHList[A <: HList] {
    def leftToRight: Ordering[A]
    def rightToLeft: Ordering[A]
  }

  object OrderingOfHList {
    /** Helpers to derive implicts */
    def leftToRight[A <: HList](implicit ev: OrderingOfHList[A]): Ordering[A] = ev.leftToRight
    def rightToLeft[A <: HList](implicit ev: OrderingOfHList[A]): Ordering[A] = ev.rightToLeft

    /** Implicit for HNil
      * Note that this implicit computes both
      * left-to-right and right-to-left orderings.
      *
      * To add a new ordering, both the type-class
      * and this implicit need to be modified.
      */
    implicit val orderingOfHNil: OrderingOfHList[HNil] =
      new OrderingOfHList[HNil] {
        val leftToRight: Ordering[HNil] =
          new Ordering[HNil] {
            def compare(x: HNil, y: HNil): Int = 0
          }

        val rightToLeft: Ordering[HNil] =
          new Ordering[HNil] {
            def compare(x: HNil, y: HNil): Int = 0
          }
      }
      
    /** Implicit for HCons
      * Note that this implicit computes both
      * left-to-right and right-to-left orderings too.
      *
      * To add a new ordering, once again, both the type-class
      * and this implicit need to be modified.
      */
    implicit def orderingOfHCons[H, T <: HList](implicit
        ordH: Ordering[H],
        ordT: OrderingOfHList[T])
      : OrderingOfHList[H ::: T] =
      new OrderingOfHList[H ::: T] {
        val leftToRight: Ordering[H ::: T] =
          new Ordering[H ::: T] {
            def compare(x: H ::: T, y: H ::: T): Int =
              ordH.compare(x.head, y.head) match {
                case 0 => ordT.leftToRight.compare(x.tail, y.tail)
                case n => n
              }
          }
        
        val rightToLeft: Ordering[H ::: T] =
          new Ordering[H ::: T] {
            def compare(x: H ::: T, y: H ::: T): Int =
              ordT.rightToLeft.compare(x.tail, y.tail) match {
                case 0 => ordH.compare(x.head, y.head)
                case n => n
              }
          }
      }
  }

  /* I guess you already know what this code is doing ;) */
  def test(): Unit = {
    val l2r = OrderingOfHList.leftToRight[Int ::: String ::: HNil].log
    val r2l = OrderingOfHList.rightToLeft[Int ::: String ::: HNil].log

    assert(l2r.compare(1 ::: "a" ::: HNil(), 1 ::: "a" ::: HNil()) ==  0)
    assert(r2l.compare(1 ::: "a" ::: HNil(), 1 ::: "a" ::: HNil()) ==  0)
    assert(l2r.compare(1 ::: "a" ::: HNil(), 1 ::: "b" ::: HNil()) == -1)
    assert(r2l.compare(1 ::: "a" ::: HNil(), 1 ::: "b" ::: HNil()) == -1)
    assert(l2r.compare(1 ::: "b" ::: HNil(), 2 ::: "a" ::: HNil()) == -1)
    assert(r2l.compare(1 ::: "b" ::: HNil(), 2 ::: "a" ::: HNil()) ==  1)
    assert(l2r.compare(2 ::: "a" ::: HNil(), 1 ::: "b" ::: HNil()) ==  1)
    assert(r2l.compare(2 ::: "a" ::: HNil(), 1 ::: "b" ::: HNil()) == -1)
  }
}

/** In the second approach use use a Generalized Algebraic Data Type
  * to store all the information we need but we do not compute
  * neither left-to-right nor right-to-left orderings yet!
  */
object SecondTry {
  /* Note that this is not really a type-class anymore!
   * Instead of an open trait that could be extended at will
   * like in the first try, OrderingOfHList is here a sealed
   * abstract class. Its only subclasses with be OrderingOfHNil
   * and OrderingOfHCons.
   */
  sealed abstract class OrderingOfHList[A]
  
  /** Note that unlike in the first try,
    * this time OrderingOfHNil does not compute
    * neither left-to-right nor right-to-left orderings.
    * It actually computes nothing at all.
    */
  final case object OrderingOfHNil
    extends OrderingOfHList[HNil]

  /** Note that unlike in the first try,
    * this time OrderingOfHCons does not compute
    * neither left-to-right nor right-to-left orderings.
    * It just stores the Ordering of H and the
    * OrderingOfHList of T.
    * Again nothing is computed, but all the
    * necessary ingredients are stored for futute use.
    */
  final case class  OrderingOfHCons[H, T <: HList](
      head: Ordering[H],
      tail: OrderingOfHList[T])
    extends OrderingOfHList[H ::: T]


  /** We want to derive values of OrderingOfHNil automatically
    * so we still need implicits. But this time they are really
    * trivial. The only thing they do is pass their arguments
    * to the two classes classes above.
    */
  object OrderingOfHList {
    /** For future use*/
    def leftToRight[A](implicit ev: OrderingOfHList[A]): Ordering[A] = deriveLeftToRight[A](ev)
    def rightToLeft[A](implicit ev: OrderingOfHList[A]): Ordering[A] = deriveRightToLeft[A](ev)

    /** Really trivial! */
    implicit val orderingOfHNil: OrderingOfHList[HNil] = OrderingOfHNil

    /** Not that much complicated.
      * Note that there is still no ordering computed!
      */
    implicit def orderingOfHCons[H, T <: HList](implicit
        ordH: Ordering[H],
        ordT: OrderingOfHList[T])
      : OrderingOfHList[H ::: T] = OrderingOfHCons(ordH, ordT)
  }

  /* Thanks to implicits we can build automatically values of
     OrderingOfHNil[H]. But we still do not have a single ordering
     computed.

     Thanksfully a value of OrderingOfHNil[H] contains everything we
     need to build the desired ordering
  */
    

  /** Let's build the left-to-right ordering!
    * The great things with GADTs is we can pattern-match
    * them! We can inspect the structure of `ord` to build
    * the ordering.
    */
  def deriveLeftToRight[A](ord: OrderingOfHList[A]): Ordering[A] =
    new Ordering[A] {
      def compare(x: A, y: A): Int =
        ord match {
          case OrderingOfHNil =>
            /* `ord` tells us `A` is actually HNIL.
             * Because OrderingOfHNil is of type OrderingOfHNil[HNil]
             * and nothing else.
             */
            0

          case OrderingOfHCons(head, tail) =>
            /* In this case, `ord` tells us `A` is actually `H ::: T` for
             * some H and T. We do not know what H and T are but fortunately
             * `head` and `tail` provide us everything we need!
             */
            head.compare(x.head, y.head) match {
              case 0 => deriveLeftToRight(tail).compare(x.tail, y.tail)
              case n => n
            }
        }
    }

  /** Let's build the right-to-left ordering now!
    * This is very similar to the opposite side.
    */
  def deriveRightToLeft[A](ord: OrderingOfHList[A]): Ordering[A] =
    new Ordering[A] {
      def compare(x: A, y: A): Int =
        ord match {
          case OrderingOfHNil =>
            0

          case OrderingOfHCons(head, tail) =>
            deriveRightToLeft(tail).compare(x.tail, y.tail) match {
              case 0 => head.compare(x.head, y.head)
              case n => n
            }
        }
    }

  /** Testing! */
  def test(): Unit = {
    val l2r = OrderingOfHList.leftToRight[Int ::: String ::: HNil].log
    val r2l = OrderingOfHList.rightToLeft[Int ::: String ::: HNil].log

    assert(l2r.compare(1 ::: "a" ::: HNil(), 1 ::: "a" ::: HNil()) ==  0)
    assert(r2l.compare(1 ::: "a" ::: HNil(), 1 ::: "a" ::: HNil()) ==  0)
    assert(l2r.compare(1 ::: "a" ::: HNil(), 1 ::: "b" ::: HNil()) == -1)
    assert(r2l.compare(1 ::: "a" ::: HNil(), 1 ::: "b" ::: HNil()) == -1)
    assert(l2r.compare(1 ::: "b" ::: HNil(), 2 ::: "a" ::: HNil()) == -1)
    assert(r2l.compare(1 ::: "b" ::: HNil(), 2 ::: "a" ::: HNil()) ==  1)
    assert(l2r.compare(2 ::: "a" ::: HNil(), 1 ::: "b" ::: HNil()) ==  1)
    assert(r2l.compare(2 ::: "a" ::: HNil(), 1 ::: "b" ::: HNil()) == -1)
  }

  /* The welcomed bonus is we can derive other ordering
   * with no modification of existing code. For example:
   */
  def deriveLeftToRightReverse[A](ord: OrderingOfHList[A]): Ordering[A] =
    new Ordering[A] {
      def compare(x: A, y: A): Int =
        ord match {
          case OrderingOfHNil =>
            0

          case OrderingOfHCons(head, tail) =>
            head.reverse.compare(x.head, y.head) match {
              case 0 => deriveLeftToRightReverse(tail).compare(x.tail, y.tail)
              case n => n
            }
        }
    }
}
}

import Test._

FirstTry.test()
SecondTry.test()