Last active
June 6, 2020 23:52
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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