Skip to content

Instantly share code, notes, and snippets.

@OlivierBlanvillain
Last active June 6, 2020 23:52
Show Gist options
  • Save OlivierBlanvillain/5f7c7c7d39f6316821b8c40c08d25c65 to your computer and use it in GitHub Desktop.
Save OlivierBlanvillain/5f7c7c7d39f6316821b8c40c08d25c65 to your computer and use it in GitHub Desktop.
Example of a workaround for the absence of backtracking in implicit resolution. Original problem statement: https://gist.github.com/atamborrino/daa451aea542e912c2d6
import shapeless.{HList, HNil, ::}
import shapeless.ops.hlist.{Selector, Prepend}
import shapeless.test.illTyped
object TypeLevelBacktrack extends App {
/** [[Parent]] / [[Child]] relationship, father side. */
trait FatherOf[Parent, Child]
/** [[Parent]] / [[Child]] relationship, mother side */
trait MotherOf[Parent, Child]
/** Typeclass computing all the [[Ancestors]] of a [[Person]]. */
trait AllAncestors[Person, Ancestors <: HList]
trait AllAncestorsLowPrio {
implicit def none[Person] = new AllAncestors[Person, HNil] {}
}
object AllAncestors extends AllAncestorsLowPrio {
implicit def fatherSide[F, P, PA <: HList]
(implicit m: FatherOf[F, P], a: AllAncestors[F, PA]) = new AllAncestors[P, F :: PA] {}
implicit def motherSide[M, P, PA <: HList]
(implicit m: MotherOf[M, P], a: AllAncestors[M, PA]) = new AllAncestors[P, M :: PA] {}
implicit def bothSides[F, M, P, FA <: HList, MA <: HList, CA <: HList]
(implicit
l: FatherOf[F, P],
r: MotherOf[M, P],
f: AllAncestors[F, FA],
m: AllAncestors[M, MA],
p: Prepend.Aux[FA, MA, CA]
) = new AllAncestors[P, F :: M :: CA] {}
}
/** Typeclass witnessing family relationship between [[P2]] and [[P1]]. */
class Relationship[P1, P2]
object Relationship {
def apply[D, A](implicit r: Relationship[D, A]): Relationship[D, A] = r
implicit def caseP2AncestorOfP1[P1, P2, A <: HList]
(implicit a: AllAncestors[P1, A], s: Selector[A, P2]) = new Relationship[P1, P2] {}
implicit def caseP1AncestorOfP2[P1, P2, A <: HList]
(implicit a: AllAncestors[P2, A], s: Selector[A, P1]) = new Relationship[P1, P2] {}
}
// Problem statement
trait Bob; trait Bill; trait Stacy; trait Ben
trait Buffy; trait Sarah; trait Philip; trait Julie
def fact[P, C](): FatherOf[P, C] = new FatherOf[P, C] {}
def fact[P, C]()(implicit d: DummyImplicit): MotherOf[P, C] = new MotherOf[P, C] {}
implicit val fact0: Stacy MotherOf Bob = fact() // Stacy Philip
implicit val fact1: Philip FatherOf Bob = fact() // \ /
implicit val fact2: Bob FatherOf Bill = fact() // Bob Julie
implicit val fact3: Bill FatherOf Buffy = fact() // / \ /
implicit val fact4: Bob FatherOf Ben = fact() // Bill Ben
implicit val fact5: Julie MotherOf Ben = fact() // | \
implicit val fact6: Ben FatherOf Sarah = fact() // Buffy Sarah
// Bob is in Relationship with everyone except Julie
Relationship[Bob, Bill]
Relationship[Bob, Stacy]
Relationship[Bob, Ben]
Relationship[Bob, Buffy]
Relationship[Bob, Sarah]
Relationship[Bob, Philip]
illTyped("Relationship[Bob, Julie]")
// Julie is only in Relationship with Ben and Sarah
Relationship[Julie, Ben]
Relationship[Julie, Sarah]
illTyped("Relationship[Julie, Bob]")
illTyped("Relationship[Julie, Bill]")
illTyped("Relationship[Julie, Stacy]")
illTyped("Relationship[Julie, Buffy]")
illTyped("Relationship[Julie, Philip]")
// Original test cases
Relationship[Bob, Bill]
Relationship[Stacy, Bill]
Relationship[Stacy, Buffy]
illTyped("Relationship[Ben, Bill]")
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment