Skip to content

Instantly share code, notes, and snippets.

@travisbrown
Last active October 4, 2017 07:38
Show Gist options
  • Save travisbrown/6a08ed57ca2f414955184aad81f8f274 to your computer and use it in GitHub Desktop.
Save travisbrown/6a08ed57ca2f414955184aad81f8f274 to your computer and use it in GitHub Desktop.
Aphyr's n-queens solution from Typing the technical interview, but 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 = ???
}
@ilya-murzinov
Copy link

@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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment