Aphyr's n-queens solution from Typing the technical interview, but Scala

queens.scala

class Nil
class Cons[X, Xs]

class First[List] { type X }
object First {
  type Aux[List, X0] = First[List] { type X = X0 }

  implicit val nilFirst: Aux[Nil, Nil] = ???
  implicit def consFirst[X0, Xs]: Aux[Cons[X0, Xs], X0] = ???
}

class ListConcat[A, B] { type C }
object ListConcat {
  type Aux[A, B, C0] = ListConcat[A, B] { type C = C0 }

  implicit def nilListConcat[X]: Aux[Nil, X, X] = ???
  implicit def consListConcat[A, As, Bs](implicit
    lc: ListConcat[As, Bs]
  ): Aux[Cons[A, As], Bs, Cons[A, lc.C]] = ???
}

class ListConcatAll[Ls] { type L }
object ListConcatAll {
  type Aux[Ls, L0] = ListConcatAll[Ls] { type L = L0 }

  implicit val nilListConcatAll: Aux[Nil, Nil] = ???
  implicit def consListConcatAll[Chunk, Rest, Acc](implicit
    lca: Aux[Rest, Acc],
    lc: ListConcat[Chunk, Acc]
  ): Aux[Cons[Chunk, Rest], lc.C] = ???
}

class True
class False

class AnyTrue[List] { type T }
object AnyTrue {
  type Aux[List, T0] = AnyTrue[List] { type T = T0 }

  implicit val nilAnyTrue: Aux[Nil, False] = ???
  implicit def consAnyTrue0[More]: Aux[Cons[True, More], True] = ???
  implicit def consAnyTrue1[List, T](implicit
    at: AnyTrue[List]
  ): Aux[Cons[False, List], at.T] = ???
}

class Not[B1] { type B }
object Not {
  type Aux[B1, B0] = Not[B1] { type B = B0 }

  implicit val falseNot: Aux[False, True] = ???
  implicit val trueNot: Aux[True, False] = ???
}

class Or[B1, B2] { type B }
object Or {
  type Aux[B1, B2, B0] = Or[B1, B2] { type B = B0 }

  implicit val trueTrueOr: Aux[True, True, True] = ???
  implicit val trueFalseOr: Aux[True, False, True] = ???
  implicit val falseTrueOr: Aux[False, True, True] = ???
  implicit val falseFalseOr: Aux[False, False, False] = ???
}

class Z
class S[N]

type N0 = Z
type N1 = S[N0]
type N2 = S[N1]
type N3 = S[N2]
type N4 = S[N3]
type N5 = S[N4]
type N6 = S[N5]
type N7 = S[N6]
type N8 = S[N7]

class PeanoEqual[A, B] { type T }
object PeanoEqual {
  type Aux[A, B, T0] = PeanoEqual[A, B] { type T = T0 }

  implicit val zZPeanoEqual: Aux[Z, Z, True] = ???
  implicit def sZPeanoEqual[A]: Aux[S[A], Z, False] = ???
  implicit def zSPeanoEqual[B]: Aux[Z, S[B], False] = ???
  implicit def ssPeanoEqual[A, B](implicit
    pe: PeanoEqual[A, B]
  ): Aux[S[A], S[B], pe.T] = ???
}

class PeanoLt[A, B] { type T }
object PeanoLt {
  type Aux[A, B, T0] = PeanoLt[A, B] { type T = T0 }

  implicit val zZPeanoLt: Aux[Z, Z, False] = ???
  implicit def sZPeanoLt[A]: Aux[S[A], Z, False] = ???
  implicit def zSPeanoLt[B]: Aux[Z, S[B], True] = ???
  implicit def ssPeanoLt[A, B](implicit
    pl: PeanoLt[A, B]
  ): Aux[S[A], S[B], pl.T] = ???
}

class PeanoAbsDiff[A, B] { type C }
object PeanoAbsDiff {
  type Aux[A, B, C0] = PeanoAbsDiff[A, B] { type C = C0 }

  implicit val zZPeanoAbsDiff: Aux[Z, Z, Z] = ???
  implicit def sZPeanoAbsDiff[A]: Aux[S[A], Z, S[A]] = ???
  implicit def zSPeanoAbsDiff[B]: Aux[Z, S[B], S[B]] = ???
  implicit def ssPeanoAbsDiff[A, B](implicit
    pa: PeanoAbsDiff[A, B]
  ): Aux[S[A], S[B], pa.C] = ???
}

class Range[N] { type Xs }
object Range {
  type Aux[N, Xs0] = Range[N] { type Xs = Xs0 }

  implicit val nilRange: Aux[Z, Nil] = ???
  implicit def consRange[N](implicit
    r: Range[N]
  ): Aux[S[N], Cons[N, r.Xs]] = ???
}

class Conj1[List]

class Apply[F, A] { type R }
object Apply {
  type Aux[F, A, R0] = Apply[F, A] { type R = R0 }

  implicit def conjApply[List, X]: Aux[Conj1[List], X, Cons[X, List]] = ???
}

class Map[F, Xs] { type Ys }
object Map {
  type Aux[F, Xs, Ys0] = Map[F, Xs] { type Ys = Ys0 }

  implicit def nilMap[F]: Aux[F, Nil, Nil] = ???
  implicit def consMap[F, X, Xs](implicit
    a: Apply[F, X],
    m: Map[F, Xs]
  ): Aux[F, Cons[X, Xs], Cons[a.R, m.Ys]] = ???
}

class MapCat[F, Xs] { type Zs }
object MapCat {
  type Aux[F, Xs, Zs0] = MapCat[F, Xs] { type Zs = Zs0 }

  implicit def nilMapCat[F]: Aux[F, Nil, Nil] = ???
  implicit def consMapCat[F, Xs, Chunks](implicit
    m: Map.Aux[F, Xs, Chunks],
    lca: ListConcatAll[Chunks]
  ): Aux[F, Xs, lca.L] = ???
}

class AppendIf[Pred, X, Ys] { type Zs }
object AppendIf {
  type Aux[Pred, X, Ys, Zs0] = AppendIf[Pred, X, Ys] { type Zs = Zs0 }

  implicit def trueAppendIf[X, Ys]: Aux[True, X, Ys, Cons[X, Ys]] = ???
  implicit def falseAppendIf[X, Ys]: Aux[False, X, Ys, Ys] = ???
}

class Filter[F, Xs] { type Ys }
object Filter {
  type Aux[F, Xs, Ys0] = Filter[F, Xs] { type Ys = Ys0 }

  implicit def nilFilter[F]: Aux[F, Nil, Nil] = ???
  implicit def consFilter[F, X, T, Xs, Ys](implicit
    a: Apply.Aux[F, X, T],
    f: Filter.Aux[F, Xs, Ys],
    ai: AppendIf[T, X, Ys]
  ): Aux[F, Cons[X, Xs], ai.Zs] = ???
}

class Queen[X, Y]
class Queen1[X]

object Queen1 {
  implicit def queen1Apply[X, Y]: Apply.Aux[Queen1[X], Y, Queen[X, Y]] = ???
}

class QueensInRow[N, X] { type Queens }
object QueensInRow {
  type Aux[N, X, Queens0] = QueensInRow[N, X] { type Queens = Queens0 }

  implicit def queensInRow[N, X, Ys](implicit
    r: Range.Aux[N, Ys],
    m: Map[Queen1[X], Ys]
  ): Aux[N, X, m.Ys] = ???
}

class Threatens[A, B] { type T }
object Threatens {
  type Aux[A, B, T0] = Threatens[A, B] { type T = T0 }

  implicit def threatens[Ax, Bx, Ay, By, XEq, YEq, XyEq, Dx, Dy, DEq](implicit
    pe1: PeanoEqual.Aux[Ax, Bx, XEq],
    pe2: PeanoEqual.Aux[Ay, By, YEq],
    or1: Or.Aux[XEq, YEq, XyEq],
    pa1: PeanoAbsDiff.Aux[Ax, Bx, Dx],
    pa2: PeanoAbsDiff.Aux[Ay, By, Dy],
    pe3: PeanoEqual.Aux[Dx, Dy, DEq],
    or2: Or[XyEq, DEq]
  ): Aux[Queen[Ax, Ay], Queen[Bx, By], or2.B] = ???
}

class Threatens1[A]
object Threatens1 {
  implicit def threatens1Apply[A, B](implicit
    t: Threatens[A, B]
  ): Apply.Aux[Threatens1[A], B, t.T] = ???
}

class Safe[Config, Queen] { type T }
object Safe {
  type Aux[Config, Queen, T0] = Safe[Config, Queen] { type T = T0 }

  implicit def safe[Queen, Config, M1, T1](implicit
    m: Map.Aux[Threatens1[Queen], Config, M1],
    at: AnyTrue.Aux[M1, T1],
    n: Not[T1]
  ): Aux[Config, Queen, n.B] = ???
}

class Safe1[Config]
object Safe1 {
  implicit def safe1Apply[Config, Queen](implicit
    s: Safe[Config, Queen]
  ): Apply.Aux[Safe1[Config], Queen, s.T] = ???
}

class AddQueen[N, X, C] { type Cs }
object AddQueen {
  type Aux[N, X, C, Cs0] = AddQueen[N, X, C] { type Cs = Cs0 }

  implicit def addQueen[N, X, C, Candidates, Filtered](implicit
    qr: QueensInRow.Aux[N, X, Candidates],
    f: Filter.Aux[Safe1[C], Candidates, Filtered],
    m: Map[Conj1[C], Filtered]
  ): Aux[N, X, C, m.Ys] = ???
}

class AddQueen2[N, X]
object AddQueen2 {
  implicit def addQueen2Apply[N, X, C](implicit
    aq: AddQueen[N, X, C]
  ): Apply.Aux[AddQueen2[N, X], C, aq.Cs] = ???
}

class AddQueenToAll[N, X, Cs] { type CsP }
object AddQueenToAll {
  type Aux[N, X, Cs, CsP0] = AddQueenToAll[N, X, Cs] { type CsP = CsP0 }

  implicit def addQueenToAllApply[N, X, Cs](implicit
    mc: MapCat[AddQueen2[N, X], Cs]
  ): Aux[N, X, Cs, mc.Zs] = ???
}

class AddQueens[N, X, Cs] { type CsP }
object AddQueens {
  type Aux[N, X, Cs, CsP0] = AddQueens[N, X, Cs] { type CsP = CsP0 }

  implicit def addQueens[X, N, Pred, Cs, CsP](implicit
    pl: PeanoLt.Aux[X, N, Pred],
    aqi: shapeless.Lazy[AddQueensIf.Aux[Pred, N, X, Cs, CsP]]
  ): Aux[N, X, Cs, CsP] = ???
}

class AddQueensIf[Pred, N, X, Cs] { type CsP }
object AddQueensIf {
  type Aux[Pred, N, X, Cs, CsP0] =
    AddQueensIf[Pred, N, X, Cs] { type CsP = CsP0 }

  implicit def addQueensIfFalse[N, X, Cs]: Aux[False, N, X, Cs, Cs] = ???
  implicit def addQueensIfTrue[N, X, Cs, Cs2, CsP](implicit
    aqta: AddQueenToAll.Aux[N, X, Cs, Cs2],
    aq: AddQueens.Aux[N, S[X], Cs2, CsP]
  ): Aux[True, N, X, Cs, CsP] = ???
}

class Solution[N] { type C }
object Solution {
  type Aux[N, C0] = Solution[N] { type C = C0 }

  implicit def solution[N, Cs](implicit
    aq: AddQueens.Aux[N, Z, Cons[Nil, Nil], Cs],
    f: First[Cs]
  ): Aux[N, f.X] = ???

  def apply[N](implicit s: Solution[N]): s.C = ???
}

Note that we need Shapeless's Lazy to step around Scala's super conservative divergence checker in the mutually recursive AddQueens / AddQueensIf type classes. Otherwise it's a pretty literal translation of @aphyr's Haskell version.

For example:

scala> :type Solution[N4]
Cons[Queen[S[S[S[Z]]],S[Z]],Cons[Queen[S[S[Z]],S[S[S[Z]]]],Cons[Queen[S[Z],Z],Cons[Queen[Z,S[S[Z]]],Nil]]]]

scala> :type Solution[N5]
Cons[Queen[S[S[S[S[Z]]]],S[Z]],Cons[Queen[S[S[S[Z]]],S[S[S[Z]]]],Cons[Queen[S[S[Z]],Z],Cons[Queen[S[Z],S[S[Z]]],Cons[Queen[Z,S[S[S[S[Z]]]]],Nil]]]]]

I'm still waiting on N6.

@travisbrown this doesn't work for N5 and greater:

<console>:12: q2.this.Map.consMap is not a valid implicit value for q2.Map[q2.AddQueen2[q2.S[q2.S[q2.N3]],q2.S[q2.Z]],q2.Cons[q2.Cons[q2.Queen[q2.Z,q2.Z],q2.Nil],q2.Nil]] because:
hasMatchingSymbol reported error: diverging implicit expansion for type q2.Map[q2.Queen1[q2.S[q2.Z]],q2.Cons[q2.S[q2.S[q2.S[q2.Z]]],q2.Cons[q2.S[q2.S[q2.Z]],q2.Cons[q2.S[q2.Z],q2.Cons[q2.Z,q2.Nil]]]]]
starting with method consMap in object Map q2.Solution[q2.N5]

. . .

<console>:12: error: could not find implicit value for parameter s: q2.Solution[q2.N5]
       q2.Solution[q2.N5]

You have to wrap m: Map[F, Xs] inside consMap in Lazy as well.