Example of a workaround for the absence of backtracking in implicit resolution. Original problem statement: https://gist.github.com/atamborrino/daa451aea542e912c2d6

TypeLevelBacktrack.scala

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]")
}