Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment