# sudoku using Func

in

This is the 5th entry of Scalaz Advent Calendar 2012.

During the months of December, tech-savvy geeks in Japan take turns to post themed blog articles, known as the "Advent Calendar". For last year's Scala Advent Calendar 2011 I translated Eric Torreborre's post covering The Essence of Iterator Pattern. It was somewhat of a calculated move, knowing Japanese fondness for functional programming articles. Another selfish motive was that some of the concept would seep in to my thickness as I was translating the post word by word. In hindsight, both goals were achieved handsomely thanks to the quality of both Jeremy Gibbons, Bruno Oliveira and Eric's work. This seeped in knowledge was probably the secret sauce behind the learning Scalaz series that I worked on this year.

As covered in learning Scalaz day 12 Scalaz 7 already included `product` and `compose` methods in typeclass instances as well as `Traverse`. It even has the word count example from the paper. What I realized missing was the value-level composition. One of the interesting points from the paper was "composition of applicative functors," which enables a kind of modular programming.

By "applicative functors" Gibbons and Oliveira actually mean composition of applicative functions, not just the typeclass instances. This is evident in the following snippet from the paper:

```data (m ⊠ n) a = Prod { pfst :: m a, psnd :: n a }
(⊗) :: (Functor m, Functor n) ⇒ (a → m b) → (a → n b) → (a → (m ⊠ n) b)
(f ⊗ g) x = Prod(f x)(gx)```

The algebraic data type `⊠` is the type-level product, while the infix function `⊗` is the value-level product of two applicative functions, which returns applicative function of type `a → (m ⊠ n)`. In other words, the programmer would construct functions that return an applicative functor, and the type-level compositions are done automatically.

### Func

`Func` is my attempt to provide value-level composition of applicative functions.

```scala> import scalaz._, Scalaz._, typelevel._
import scalaz._
import Scalaz._
import typelevel._

scala> val f = AppFuncU { (x: Int) => x + 1 }
f: scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,Int]{type M[X] = Int; type A = Int}#M,scalaz.Applicative,Int,Int] = scalaz.typelevel.FuncFunctions\$\$anon\$12@3143369a

scala> val g = AppFuncU { (x: Int) => List(x, 5) }
g: scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,List[Int]]{type M[X] = List[X]; type A = Int}#M,scalaz.Applicative,Int,Int] = scalaz.typelevel.FuncFunctions\$\$anon\$12@3106a3a2

scala> (f @&&& g) traverse List(1, 2, 3)
res0: scalaz.typelevel.TCCons[scalaz.Unapply[scalaz.Applicative,Int]{type M[X] = Int; type A = Int}#M,scalaz.typelevel.TCCons[scalaz.Unapply[scalaz.Applicative,List[Int]]{type M[X] = List[X]; type A = Int}#M,scalaz.typelevel.TCNil]]#Product[List[Int]] = GenericCons(9,GenericCons(List(List(1, 2, 3), List(1, 2, 5), List(1, 5, 3), List(1, 5, 5), List(5, 2, 3), List(5, 2, 5), List(5, 5, 3), List(5, 5, 5)),GenericNil()))```

Similar to `Kleisli`, `Func` represents a function `A => F[B]`:

```trait Func[F[_], TC[F[_]] <: Functor[F], A, B] { self =>
def runA(a: A): F[B]
implicit def TC: KTypeClass[TC]
implicit def F: TC[F]
}```

The `runA` method runs the function, similar to `apply` method.

`Func` also implements `productA` method (symbolic alias `@&&&`), which returns another `Func`. The original implementation of `Func` was called `AppFunc` and it was specialized to applicative functors. Per suggestion by Lars Hupel (@larsr_h) it was refactored to be `Func` that is generic over typeclass.

### scalaz-typelevel module

The `product` and `compose` methods implemented at individual typeclass in core module are independent from each other since they do not share the same signature. For example, `product` under `Functor` returns `Functor[({type λ[α] = (F[α], G[α])})#λ]`, and `product` under `Applicative` returns `Applicative[({type λ[α] = (F[α], G[α])})#λ]`.

The scalaz-typelevel module contains type-level data structure (and also type-safe printf according to the readme). What I am after is `KTypeClass`, which is a typeclass of typeclasses with kind `* -> *` like `Functor` and `Applicative`. Its main feature is generic `product` and `compose` methods:

```trait KTypeClass[C[_[_]]] {
def product[F[_], T <: TCList](FHead: C[F], FTail: C[T#Product]): C[TCCons[F, T]#Product]
def compose[F[_], T <: TCList](FOuter: C[F], FInner: C[T#Composed]): C[TCCons[F, T]#Composed]
}```

Instead of using `Tuple2` to encode products, `KTypeClass` uses an `HList` to encode products. This is also included in scalaz-typelvel module. Unlike a `List` that is limited to preserving one type for all elements, `HList` preserves all types of the elements:

```scala> List(1, "string").head
res1: Any = 1

scala> (1 :: "string" :: HNil).head
res2: scalaz.Id.Id[Int] = 1```

To accommodate both `Int` and `String` the first `List` was widened to `List[Any]` while `HList` preserved the type.

### HListFunc

Following EIP, my implmenetation of `Func` only supported product of two functions using `@&&&` operator. If someone were to chain `@&&&`, it would nest an `HList` within an `HList`. Lars suggested that we should be able to grow the `HList` instead.

After a few weeks I've come up with `HListFunc`, a wrapper function that returns an `HList`, which extends `Func`:

```trait HListFunc[T <: TCList, TC[X[_]] <: Functor[X], A, B] extends Func[T#Product, TC, A, B] { self =>
def ::[G[_]](g: Func[G, TC, A, B]) = g consA self
private[scalaz] def Product: KTypeClass.WrappedProduct[TC, T]
final def F = Product.instance
}```

There are two ways of creating an `HListFunc`. First, is to call `HNil` method under one of the specialized `Func` objects such as `AppFunc`:

```scala> AppFunc.HNil
res7: scalaz.typelevel.HListFunc[scalaz.typelevel.TCNil,scalaz.Applicative,Nothing,Nothing] = scalaz.typelevel.FuncFunctions\$\$anon\$6@1e525ac8

scala> AppFunc.HNil[Int, Int]
res8: scalaz.typelevel.HListFunc[scalaz.typelevel.TCNil,scalaz.Applicative,Int,Int] = scalaz.typelevel.FuncFunctions\$\$anon\$6@6e8d1f6a

scala> res8.runA(0)
res9: scalaz.typelevel.TCNil#Product[Int] = GenericNil()```

The second way of creating an `HListFunc` is to use `::` operator on an existing `HListFunc`:

```scala> AppFuncU { (x: Int) => x + 1 } :: AppFunc.HNil
res15: scalaz.typelevel.HListFunc[scalaz.typelevel.TCCons[scalaz.Unapply[scalaz.Applicative,Int]{type M[X] = Int; type A = Int}#M,scalaz.typelevel.TCNil],scalaz.Applicative,Int,Int] = scalaz.typelevel.Func\$\$anon\$4@34f262c3```

### Func again

Using `HListFunc` the `productA` (or `@&&&`) method is implemented as follows:

```  /** compose `A => F[B]` and `A => G[B]` into `A => F[B] :: G[B] :: HNil` */
def productA[G[_]](g: Func[G, TC, A, B]) = consA(g consA hnilfunc[TC, A, B])```

`Func` also implements `composeA` method with symbolic alias `<<<@`, and its flip `andThenA` method with symbolic alias `@>>>`:

```scala> AppFuncU { (x: Int) => (x + 1).some } @>>> AppFuncU { (x: Int) => x + "!" }
res32: scalaz.typelevel.Func[[α]scalaz.Unapply[scalaz.Applicative,Option[Int]]{type M[X] = Option[X]; type A = Int}#M[scalaz.Unapply[scalaz.Applicative,String]{type M[X] = String; type A = String}#M[α]],scalaz.Applicative,Int,String] = scalaz.typelevel.Func\$\$anon\$7@4fcb8010

scala> res32.runA(10)
res33: scalaz.Unapply[scalaz.Applicative,Option[Int]]{type M[X] = Option[X]; type A = Int}#M[scalaz.Unapply[scalaz.Applicative,String]{type M[X] = String; type A = String}#M[String]] = Some(11!)```

## sudoku

The first thing that came to my mind to demonstrate applicative composition using `Func` was writing a sudoku solver. It should be complex enough to bring out some of the strength and weakness of the tool. It may not be the best way to solve sudoku.

Here's an example of simple sudoku file format I found online:

``````#C comment
2..1.5..3
.54...71.
.1.2.3.8.
6.28.73.4
.........
1.53.98.6
.2.7.1.6.
.81...24.
7..4.2..1
``````

Lines starting with `#` are headers, and the rest of the lines denote a puzzle. For the sake of simplicity I am going first solve the following 4x4 sudoku first:

``````#C comment
.13.
...4
...1
.24.
``````

We can represent each spot as a cell defined as follows:

`case class Cell(pos: (Int, Int), value: Option[Int])`

Parsing a file into `Vector[Cell]` is trivial.

```object Reader {
import scalaz._
import Scalaz._

def read(file: File): Vector[Cell] = {
val source = scala.io.Source.fromFile(file, "UTF-8")
val lines = Vector(source.getLines.toSeq filterNot { x => x.isEmpty || (x startsWith "#") }: _*)
lines.zipWithIndex flatMap { case (line, idx) =>
val cs = Vector(line.toSeq: _*)
(1 |-> lines.size) map { x =>
Cell((x, idx + 1), cs(x - 1).toString.parseInt.toOption)
}
}
}
}```

We can confirm this from the REPL:

```scala> import com.eed3si9n.sudoku._
import com.eed3si9n.sudoku._

res0: Vector[com.eed3si9n.sudoku.Cell] = Vector(Cell((1,1),None), Cell((2,1),Some(1)), Cell((3,1),Some(3)), Cell((4,1),None), Cell((1,2),None), Cell((2,2),None), Cell((3,2),None), Cell((4,2),Some(4)), Cell((1,3),None), Cell((2,3),None), Cell((3,3),None), Cell((4,3),Some(1)), Cell((1,4),None), Cell((2,4),Some(2)), Cell((3,4),Some(4)), Cell((4,4),None))```

### splitting the work

Focusing on a particular cell, for example `(4, 1)`, how would one go about solving sudoku? I would check the column and row to eliminate possible candidates, and then check the cell's four-cell group to eliminate further candidates. This strategy works for easier puzzles.

Another way of looking at the above strategy is the process of elimination. We start out with `Vector(1, 2, 3, 4)` and each small machine can check for a row, a column, or a group, gradually eliminating the candidates. These small machines can be implemented as a `State` monad. First here's the setup:

```scala> import scalaz._, Scalaz._, typelevel._
import scalaz._
import Scalaz._
import typelevel._

scala> import com.eed3si9n.sudoku._
import com.eed3si9n.sudoku._

game: Vector[com.eed3si9n.sudoku.Cell] = Vector(Cell((1,1),None), Cell((2,1),Some(1)), ...```

Next, here's the horizontal machine:

```scala>  def horizontalMachine(pos: (Int, Int)) = AppFuncU { cell: Cell =>
for {
xs <- get[Vector[Int]]
_  <- put(if (pos._2 == cell.pos._2 && cell.value.isDefined) xs filter {_ != cell.value.get}
else xs)
} yield()
}
horizontalMachine: (pos: (Int, Int))scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.Applicative,Cell,Unit]

scala> horizontalMachine((4, 1)) traverse game
res1: scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M[Vector[Unit]] = scalaz.StateT\$\$anon\$7@33d5157f

scala> res1 exec Vector(1, 2, 3, 4)
res2: scalaz.Id.Id[Vector[Int]] = Vector(2, 4)```

The result seems to be consistent with the game since all numbers except 2 and 4 are present in the first row. We can expand this logic to the vertical machine:

```scala>  def verticalMachine(pos: (Int, Int)) = AppFuncU { cell: Cell =>
for {
xs <- get[Vector[Int]]
_  <- put(if (pos._1 == cell.pos._1 && cell.value.isDefined) xs filter {_ != cell.value.get}
else xs)
} yield()
}
verticalMachine: (pos: (Int, Int))scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.Applicative,com.eed3si9n.sudoku.Cell,Unit]

scala> verticalMachine((4, 1)) traverse game
res5: scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M[Vector[Unit]] = scalaz.StateT\$\$anon\$7@70a81b43

scala> res5 exec Vector(1, 2, 3, 4)
res6: scalaz.Id.Id[Vector[Int]] = Vector(2, 3)```

`for` comprehension part can be refactored out as follows:

```scala>  def buildMachine(predicate: Cell => Boolean) = AppFuncU { cell: Cell =>
for {
xs <- get[Vector[Int]]
_  <- put(if (predicate(cell)) xs filter {_ != cell.value.get}
else xs)
} yield()
}
buildMachine: (predicate: com.eed3si9n.sudoku.Cell => Boolean)scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.Applicative,com.eed3si9n.sudoku.Cell,Unit]

scala>  def verticallMachine(pos: (Int, Int)) =
buildMachine { cell: Cell => pos._1 == cell.pos._1 && cell.value.isDefined }
verticallMachine: (pos: (Int, Int))scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.Applicative,com.eed3si9n.sudoku.Cell,Unit]```

Using `buildMachine`, we can define `groupMachine` as follows:

```scala>  def groupMachine(pos: (Int, Int), n: Int) =
buildMachine { cell: Cell =>
((pos._1 - 1) / n == (cell.pos._1 - 1) / n) &&
((pos._2 - 1) / n == (cell.pos._2 - 1) / n) &&
cell.value.isDefined
}
groupMachine: (pos: (Int, Int), n: Int)scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.Applicative,com.eed3si9n.sudoku.Cell,Unit]

scala> groupMachine((4, 1)) traverse game
res7: scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M[Vector[Unit]] = scalaz.StateT\$\$anon\$7@79f39896

scala> res7 exec Vector(1, 2, 3, 4)
res8: scalaz.Id.Id[Vector[Int]] = Vector(1, 2)```

Next, we would like to run all three machines in parallel. We can construct `HListFunc` as follows:

```scala>  def threeMachines(pos: (Int, Int), n: Int) =
horizontalMachine(pos) :: verticalMachine(pos) :: groupMachine(pos, n) :: AppFunc.HNil
threeMachines: ...```

The problem here is that this now returns a `Func` that returns an `HList`. We would like a `List` instead since all three elements contain the same type.

### homogenizing hlist

To fold an hlist into something we would define a `HFold` subtype as follows:

```scala>  class Homogenize[T] extends HFold[Id, List[T]] {
type Init = List[T]
def init = Nil
type Apply[E, A <: List[T]] = List[T]
def apply[E, A <: List[T]](elem: E, acc: A) =
(elem match {
case x: T => x
}) :: acc
}
defined class Homogenize```

By using this, we can now turn `HListFunc` into a `Func` that returns a list of state monads:

```scala>  def homogenize[M[_]: Applicative, T <: TCList, B](g: HListFunc[TCCons[M, T], Applicative, Cell, B]) =
new Func[({type λ[α] = List[M[α]]})#λ, Applicative, Cell, B] {
def runA(c: Cell): List[M[B]] = {
val xs = g.runA(c)
xs.fold[Id, List[M[B]], Homogenize[M[B]]](new Homogenize)
}
def F = (Applicative[List] <<: Applicative[M] <<: TC.idCompose).instance
def TC = g.TC
}
homogenize: [M[_], T <: scalaz.typelevel.TCList, B](g: scalaz.typelevel.HListFunc[scalaz.typelevel.TCCons[M,T],scalaz.Applicative,com.eed3si9n.sudoku.Cell,B])(implicit evidence\$1: scalaz.Applicative[M])scalaz.typelevel.Func[[α]List[M[α]],scalaz.Applicative,com.eed3si9n.sudoku.Cell,B]```

Then we can go even further by turning the list of state monad into a state monad of a list:

```scala>  def sequence[M[_]: Applicative, T <: TCList, B](g: HListFunc[TCCons[M, T], Applicative, Cell, B]) =
new Func[M, Applicative, Cell, List[B]] {
def runA(c: Cell): M[List[B]] = {
val xs = g.runA(c)
val list: List[M[B]] = xs.fold[Id, List[M[B]], Homogenize[M[B]]](new Homogenize)
list.sequence
}
def F = Applicative[M]
def TC = g.TC
}
sequence: [M[_], T <: scalaz.typelevel.TCList, B](g: scalaz.typelevel.HListFunc[scalaz.typelevel.TCCons[M,T],scalaz.Applicative,com.eed3si9n.sudoku.Cell,B])(implicit evidence\$1: scalaz.Applicative[M])scalaz.typelevel.Func[M,scalaz.Applicative,com.eed3si9n.sudoku.Cell,List[B]]```

The above should chain the state monads together. Let's try it for `(4, 1)`:

```scala> sequence(threeMachines((4, 1), 2)) traverse game
res10: scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M[Vector[List[Unit]]] = scalaz.StateT\$\$anon\$7@3fc1c1a6

scala> res10 exec Vector(1, 2, 3, 4)
res11: scalaz.Id.Id[Vector[Int]] = Vector(2)```

Let's call this a `cellMachine`:

```object Solver {
def solve(game: Vector[Cell]) {

}
def cellMachine(pos: (Int, Int), n: Int) =
sequence(horizontalMachine(pos) :: verticalMachine(pos) :: groupMachine(pos, n) :: AppFunc.HNil)
...
}```

### running for all cells

We can now run the `cellMachine` for all empty cells to see the progress so far:

```object Solver {
...
def runOnce(game: Vector[Cell]) {
val css = game map { cell: Cell =>
val cs = cell.value map { v =>
Vector(v)
} getOrElse {
(cellMachine(cell.pos, 2) traverse game) exec Vector(1, 2, 3, 4)
}
if (cell.pos._1 == 1) println()
print(cs.toString + " ")
cs
}
}
}```

Here's `game` again:

``````#C comment
.13.
...4
...1
.24.
``````

Let's run `runOnce`:

```scala> Solver.runOnce(game)

Vector(2, 4) Vector(1) Vector(3) Vector(2)
Vector(2, 3) Vector(3) Vector(1, 2) Vector(4)
Vector(3, 4) Vector(3, 4) Vector(2) Vector(1)
Vector(1, 3) Vector(2) Vector(4) Vector(3) ```

Using this information, we can now return a new `Vector[Cell]`. First, let's expand the definition of `Cell` to store potential candidates:

```scala> case class Cell(pos: (Int, Int),
value: Option[Int],
cs: Vector[Int] = Vector())
defined class Cell```

Also we should probably create a `Game` class instead of passing vectors around:

```case class Game(cells: Vector[Cell]) {
import scalaz._
import Scalaz._

val n: Int = math.pow(cells.size, 0.5).round.toInt
val sqrtn: Int = math.pow(n, 0.5).round.toInt
val allValues = Vector((1 |-> n): _*)
def apply(pos: (Int, Int)) = (cells.find {_.pos == pos}).get
override def toString: String = {
(allValues flatMap { y =>
allValues flatMap { x =>
val cell = apply((x, y))
(cell.value map { x =>
cell.value.toString
} getOrElse {cell.cs.toString}) +
(if (x == n) "\n"
else " ")
}
}).mkString
}
}```

Here's the updated `runOnce`:

```  def runOnce(game: Game): Game = {
val (nonEmptyCells, emptyCells) = game.cells partition {_.value.isDefined}
val solveCells = emptyCells map { cell =>
val candidates = (cellMachine(cell.pos, game.n) traverse game.cells) exec game.allValues
if (candidates.size == 1) cell.copy(value = candidates(0).some, cs = Vector())
else cell.copy(value = none, cs = candidates)
}
game.copy(cells = nonEmptyCells ++ solveCells)
}```

By calling `runOnce` repeatedly we are now able to solve some problems:

```scala> Solver.runOnce(game)
res0: com.eed3si9n.sudoku.Game =
Vector(2, 4) Some(1) Some(3) Some(2)
Vector(2, 3) Some(3) Vector(1, 2) Some(4)
Vector(3, 4) Vector(3, 4) Some(2) Some(1)
Vector(1, 3) Some(2) Some(4) Some(3)

scala> Solver.runOnce(res0)
res1: com.eed3si9n.sudoku.Game =
Some(4) Some(1) Some(3) Some(2)
Some(2) Some(3) Some(1) Some(4)
Vector(3, 4) Some(4) Some(2) Some(1)
Some(1) Some(2) Some(4) Some(3)

scala> Solver.runOnce(res1)
res2: com.eed3si9n.sudoku.Game =
Some(4) Some(1) Some(3) Some(2)
Some(2) Some(3) Some(1) Some(4)
Some(3) Some(4) Some(2) Some(1)
Some(1) Some(2) Some(4) Some(3)```

### all cells in parallel

Instead of traversing multiple times, let's see if we can compose machines in parallel.

```scala> val (nonEmptyCells, emptyCells) = game.cells partition {_.value.isDefined}
nonEmptyCells: ...
emptyCells: ...

scala> emptyCells.foldLeft[HListFunc[TCList, Applicative, Cell, List[Vector[Int]]]](AppFunc.HNil[Cell, List[Vector[Int]]]) { (acc, cell) => Solver.cellMachine(cell.pos, game.sqrtn) :: acc }
<console>:22: error: type mismatch;
found   : scalaz.typelevel.HListFunc[scalaz.typelevel.TCNil,scalaz.Applicative,com.eed3si9n.sudoku.Cell,List[Vector[Int]]]
required: scalaz.typelevel.HListFunc[scalaz.typelevel.TCList,scalaz.Applicative,com.eed3si9n.sudoku.Cell,List[Vector[Int]]]
Note: scalaz.typelevel.TCNil <: scalaz.typelevel.TCList, but trait HListFunc is invariant in type T.
You may wish to define T as +T instead. (SLS 4.5)
emptyCells.foldLeft[HListFunc[TCList, Applicative, Cell, List[Vector[Int]]]](AppFunc.HNil[Cell, List[Vector[Int]]]) { (acc, cell) => Solver.cellMachine(cell.pos, game.sqrtn) :: acc }
^```

We cannot use `foldLeft` because the type `TCNil` is narrower than `TCList`, and type parameter `T` of `HListFunc` is invariant. Since `HListFunc` doesn't have a general trait like `HList`, I am going to resort to constructing `HList` manually:

```scala>    def foldCells(xs: Vector[Cell], game: Game): Vector[Cell] = {
def f(cell: Cell) = Solver.cellMachine(cell.pos, game.sqrtn)
def homogenize[M[_], B, T <: HList](xs: HCons[M[B], T]): List[M[B]] =
xs.fold[Id, List[M[B]], Homogenize[M[B]]](new Homogenize)
val hnil = AppFunc.HNil[Cell, List[Unit]]
val css = if (xs.isEmpty) Nil
else if (xs.size === 1) homogenize((f(xs(0)) :: hnil) traverse game.cells) map {_ exec game.allValues}
else if (xs.size === 2) homogenize((f(xs(1)) :: f(xs(0)) :: hnil) traverse game.cells) map {_ exec game.allValues}
else if (xs.size === 3) homogenize((f(xs(2)) :: f(xs(1)) :: f(xs(0)) :: hnil) traverse game.cells) map {_ exec game.allValues}
else if (xs.size === 4) homogenize((f(xs(3)) :: f(xs(2)) :: f(xs(1)) :: f(xs(0)) :: hnil) traverse game.cells) map {_ exec game.allValues}
else sys.error("invalid")
(xs zip css.reverse) map { case (cell, cs) =>
cell.copy(cs = cs)
}
}
foldCells: (xs: Vector[com.eed3si9n.sudoku.Cell], game: com.eed3si9n.sudoku.Game)Vector[com.eed3si9n.sudoku.Cell]

scala> val cellsWithCs = Vector((emptyCells grouped 4).toSeq: _*) flatMap { g => foldCells(g, game) }
cellsWithCs: scala.collection.immutable.Vector[com.eed3si9n.sudoku.Cell] = Vector(Cell((1,1),None,Vector(2, 4)), Cell((4,1),None,Vector(2)), Cell((1,2),None,Vector(2, 3)), Cell((2,2),None,Vector(3)), Cell((3,2),None,Vector(1, 2)), Cell((1,3),None,Vector(3, 4)), Cell((2,3),None,Vector(3, 4)), Cell((3,3),None,Vector(2)), Cell((1,4),None,Vector(1, 3)), Cell((4,4),None,Vector(3)))```

The above code traverses 4 empty cells at a time.

### iterating solver

Let's implement the solver by calling `runOnce` until the game is solved.

```case class Game(cells: Vector[Cell]) {
...
def isSolved: Boolean = cells forall {_.value.isDefined}
}```

Here's the solver:

```  def solve(game: Game) {
def doLoop(g: Game) {
println(g.toString)
if (g.isSolved) println("solved")
else {
val g2 = runOnce(g)
if (g == g2) sys.error("solver is stuck")
else doLoop(g2)
}
}
doLoop(game)
}```

We already saw that this solves easy games:

```scala> Solver.solve(game)
....

Some(4) Some(1) Some(3) Some(2)
Some(2) Some(3) Some(1) Some(4)
Some(3) Some(4) Some(2) Some(1)
Some(1) Some(2) Some(4) Some(3)

solved```

Normally a game of sudoku requires a bit more thinking. For example, save the following as 3.sdk:

``````#C comment
47..6..59
...2.7...
6.......8
..5.8.9..
.1.7.6.8.
..8.4.2..
8.......2
...6.3...
92..5..16
``````

Using sbt we can load this file as `game` in REPL:

```initialCommands in console := """import scalaz._, Scalaz._, typelevel._
|import com.eed3si9n.sudoku._

Here's the output:

```scala> Solver.solve(game)
Some(4) Some(7) Vector() Vector() Some(6) Vector() Vector() Some(5) Some(9)
Vector() Vector() Vector() Some(2) Vector() Some(7) Vector() Vector() Vector()
Some(6) Vector() Vector() Vector() Vector() Vector() Vector() Vector() Some(8)
Vector() Vector() Some(5) Vector() Some(8) Vector() Some(9) Vector() Vector()
Vector() Some(1) Vector() Some(7) Vector() Some(6) Vector() Some(8) Vector()
Vector() Vector() Some(8) Vector() Some(4) Vector() Some(2) Vector() Vector()
Some(8) Vector() Vector() Vector() Vector() Vector() Vector() Vector() Some(2)
Vector() Vector() Vector() Some(6) Vector() Some(3) Vector() Vector() Vector()
Some(9) Some(2) Vector() Vector() Some(5) Vector() Vector() Some(1) Some(6)

Some(4) Some(7) Vector(1, 2, 3) Vector(1, 3, 8) Some(6) Vector(1, 8) Vector(1, 3) Some(5) Some(9)
Vector(1, 3, 5) Vector(3, 5, 8, 9) Vector(1, 3, 9) Some(2) Vector(1, 3, 9) Some(7) Vector(1, 3, 4, 6) Vector(3, 4, 6) Vector(1, 3, 4)
Some(6) Vector(3, 5, 9) Vector(1, 2, 3, 9) Vector(1, 3, 4, 5, 9) Vector(1, 3, 9) Vector(1, 4, 5, 9) Vector(1, 3, 4, 7) Vector(2, 3, 4, 7) Some(8)
Vector(2, 3, 7) Vector(3, 4, 6) Some(5) Vector(1, 3) Some(8) Vector(1, 2) Some(9) Vector(3, 4, 6, 7) Vector(1, 3, 4, 7)
Vector(2, 3) Some(1) Vector(2, 3, 4, 9) Some(7) Vector(2, 3, 9) Some(6) Vector(3, 4, 5) Some(8) Vector(3, 4, 5)
Vector(3, 7) Vector(3, 6, 9) Some(8) Vector(1, 3, 5, 9) Some(4) Vector(1, 5, 9) Some(2) Vector(3, 6, 7) Vector(1, 3, 5, 7)
Some(8) Vector(3, 4, 5, 6) Vector(1, 3, 4, 6, 7) Vector(1, 4, 9) Vector(1, 7, 9) Vector(1, 4, 9) Vector(3, 4, 5, 7) Vector(3, 4, 7, 9) Some(2)
Vector(1, 5, 7) Vector(4, 5) Vector(1, 4, 7) Some(6) Vector(1, 2, 7, 9) Some(3) Vector(4, 5, 7, 8) Vector(4, 7, 9) Vector(4, 5, 7)
Some(9) Some(2) Vector(3, 4, 7) Vector(4, 8) Some(5) Vector(4, 8) Vector(3, 4, 7, 8) Some(1) Some(6)

java.lang.RuntimeException: solver is stuck
at scala.sys.package\$.error(package.scala:27)
....```

### unique candidate

The current implementation selects a candidate when it's the only candidate. But even for a cell that has multiple candidates, if one of the candidates is unique among any of the peers, it should also be considered eligible.

```scala>  def buildEvalMachine(predicate: Cell => Boolean) = AppFuncU { cell: Cell =>
for {
xs <- get[Vector[Int]]
_  <- put(if (predicate(cell)) xs diff cell.cs
else xs)
} yield ()
}
buildEvalMachine: (predicate: com.eed3si9n.sudoku.Cell => Boolean)scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.Applicative,com.eed3si9n.sudoku.Cell,Unit]

scala>  def horizEvalMachine(pos: (Int, Int)) =
buildEvalMachine { cell: Cell => (cell.pos != pos) && (pos._2 == cell.pos._2) }
horizEvalMachine: (pos: (Int, Int))scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.Applicative,com.eed3si9n.sudoku.Cell,Unit]

scala> val cellsWithCs = Vector((emptyCells grouped 4).toSeq: _*) flatMap { g => foldCells(g, game) }
cellsWithCs: scala.collection.immutable.Vector[com.eed3si9n.sudoku.Cell] = Vector(Cell((3,1),None,Vector(1, 2, 3)), ...

scala> horizEvalMachine((3, 1)) traverse cellsWithCs
res8: scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M[scala.collection.immutable.Vector[Unit]] = scalaz.StateT\$\$anon\$7@5b06ad02

scala> res8 exec Vector(1, 2, 3)
res9: scalaz.Id.Id[Vector[Int]] = Vector(2)```

This is a nice example. The cell in position `(3, 1)` started with three candidates, but it got narrowed down to `2` using this logic. We should be able to run all three machines in parallel.

```  def evalMachine(pos: (Int, Int), n: Int) =
horizEvalMachine(pos) :: vertEvalMachine(pos) :: groupEvalMachine(pos, n) :: AppFunc.HNil```

Now we can incorporate this secondary evaluation to narrow down the candidates:

```  def runOnce(game: Game): Game = {
val (nonEmptyCells, emptyCells) = game.cells partition {_.value.isDefined}
def homogenize[M[_], B, T <: HList](xs: HCons[M[B], T]): List[M[B]] =
xs.fold[Id, List[M[B]], Homogenize[M[B]]](new Homogenize)
def foldCells(xs: Vector[Cell], game: Game): Vector[Cell] =  ...
val cellsWithCs = Vector((emptyCells grouped 4).toSeq: _*) flatMap { g => foldCells(g, game) }
val cellsWithCs2: Vector[Cell] = cellsWithCs map { x =>
val css = homogenize(evalMachine(x.pos, game.sqrtn) traverse cellsWithCs) map {_ exec x.cs}
x.copy(cs = (css find {_.size == 1}) | x.cs)
}
val solveCells = cellsWithCs2 map { cell =>
if (cell.cs.size == 1) cell.copy(value = cell.cs(0).some, cs = Vector())
else cell
}
game.copy(cells = nonEmptyCells ++ solveCells)
}```

Here's the solver output for the game that got stuck previously:

```scala> Solver.solve(game)
Some(4) Some(7) Vector() Vector() Some(6) Vector() Vector() Some(5) Some(9)
Vector() Vector() Vector() Some(2) Vector() Some(7) Vector() Vector() Vector()
Some(6) Vector() Vector() Vector() Vector() Vector() Vector() Vector() Some(8)
Vector() Vector() Some(5) Vector() Some(8) Vector() Some(9) Vector() Vector()
Vector() Some(1) Vector() Some(7) Vector() Some(6) Vector() Some(8) Vector()
Vector() Vector() Some(8) Vector() Some(4) Vector() Some(2) Vector() Vector()
Some(8) Vector() Vector() Vector() Vector() Vector() Vector() Vector() Some(2)
Vector() Vector() Vector() Some(6) Vector() Some(3) Vector() Vector() Vector()
Some(9) Some(2) Vector() Vector() Some(5) Vector() Vector() Some(1) Some(6)

Some(4) Some(7) Some(2) Vector(1, 3, 8) Some(6) Vector(1, 8) Vector(1, 3) Some(5) Some(9)
Vector(1, 3, 5) Some(8) Vector(1, 3, 9) Some(2) Vector(1, 3, 9) Some(7) Some(6) Vector(3, 4, 6) Vector(1, 3, 4)
Some(6) Vector(3, 5, 9) Vector(1, 2, 3, 9) Vector(1, 3, 4, 5, 9) Vector(1, 3, 9) Vector(1, 4, 5, 9) Vector(1, 3, 4, 7) Some(2) Some(8)
Vector(2, 3, 7) Vector(3, 4, 6) Some(5) Vector(1, 3) Some(8) Some(2) Some(9) Vector(3, 4, 6, 7) Vector(1, 3, 4, 7)
Vector(2, 3) Some(1) Vector(2, 3, 4, 9) Some(7) Vector(2, 3, 9) Some(6) Vector(3, 4, 5) Some(8) Vector(3, 4, 5)
Vector(3, 7) Vector(3, 6, 9) Some(8) Vector(1, 3, 5, 9) Some(4) Vector(1, 5, 9) Some(2) Vector(3, 6, 7) Vector(1, 3, 5, 7)
Some(8) Vector(3, 4, 5, 6) Some(6) Vector(1, 4, 9) Vector(1, 7, 9) Vector(1, 4, 9) Vector(3, 4, 5, 7) Vector(3, 4, 7, 9) Some(2)
Vector(1, 5, 7) Vector(4, 5) Vector(1, 4, 7) Some(6) Some(2) Some(3) Some(8) Vector(4, 7, 9) Vector(4, 5, 7)
Some(9) Some(2) Vector(3, 4, 7) Vector(4, 8) Some(5) Vector(4, 8) Vector(3, 4, 7, 8) Some(1) Some(6)

Some(4) Some(7) Some(2) Vector(1, 3, 8) Some(6) Vector(1, 8) Vector(1, 3) Some(5) Some(9)
Some(5) Some(8) Vector(1, 3, 9) Some(2) Vector(1, 3, 9) Some(7) Some(6) Vector(3, 4) Vector(1, 3, 4)
Some(6) Vector(3, 5, 9) Vector(1, 3, 9) Vector(1, 3, 4, 5, 9) Vector(1, 3, 9) Vector(1, 4, 5, 9) Some(7) Some(2) Some(8)
Vector(3, 7) Vector(3, 4, 6) Some(5) Vector(1, 3) Some(8) Some(2) Some(9) Vector(3, 4, 6, 7) Vector(1, 3, 4, 7)
Some(2) Some(1) Vector(3, 4, 9) Some(7) Vector(3, 9) Some(6) Vector(3, 4, 5) Some(8) Vector(3, 4, 5)
Vector(3, 7) Vector(3, 6, 9) Some(8) Vector(1, 3, 5, 9) Some(4) Vector(1, 5, 9) Some(2) Vector(3, 6, 7) Vector(1, 3, 5, 7)
Some(8) Vector(3, 4, 5) Some(6) Vector(1, 4, 9) Some(7) Vector(1, 4, 9) Vector(3, 4, 5, 7) Vector(3, 4, 7, 9) Some(2)
Vector(1, 5, 7) Vector(4, 5) Vector(1, 4, 7) Some(6) Some(2) Some(3) Some(8) Some(9) Vector(4, 5, 7)
Some(9) Some(2) Vector(3, 4, 7) Vector(4, 8) Some(5) Vector(4, 8) Vector(3, 4, 7) Some(1) Some(6)

Some(4) Some(7) Some(2) Vector(1, 3, 8) Some(6) Vector(1, 8) Some(1) Some(5) Some(9)
Some(5) Some(8) Vector(1, 3, 9) Some(2) Vector(1, 3, 9) Some(7) Some(6) Vector(3, 4) Vector(1, 3, 4)
Some(6) Vector(3, 9) Vector(1, 3, 9) Vector(1, 3, 4, 5, 9) Vector(1, 3, 9) Vector(1, 4, 5, 9) Some(7) Some(2) Some(8)
Vector(3, 7) Vector(3, 4, 6) Some(5) Vector(1, 3) Some(8) Some(2) Some(9) Vector(3, 4, 6, 7) Vector(1, 3, 4, 7)
Some(2) Some(1) Vector(3, 4, 9) Some(7) Vector(3, 9) Some(6) Vector(3, 4, 5) Some(8) Vector(3, 4, 5)
Vector(3, 7) Vector(3, 6, 9) Some(8) Vector(1, 3, 5, 9) Some(4) Vector(1, 5, 9) Some(2) Vector(3, 6, 7) Vector(1, 3, 5, 7)
Some(8) Vector(3, 4, 5) Some(6) Vector(1, 4, 9) Some(7) Vector(1, 4, 9) Vector(3, 4, 5) Vector(3, 4) Some(2)
Some(1) Vector(4, 5) Vector(1, 4, 7) Some(6) Some(2) Some(3) Some(8) Some(9) Some(7)
Some(9) Some(2) Some(7) Vector(4, 8) Some(5) Vector(4, 8) Vector(3, 4) Some(1) Some(6)

Some(4) Some(7) Some(2) Some(3) Some(6) Some(8) Some(1) Some(5) Some(9)
Some(5) Some(8) Vector(1, 3, 9) Some(2) Vector(1, 3, 9) Some(7) Some(6) Vector(3, 4) Vector(3, 4)
Some(6) Vector(3, 9) Vector(1, 3, 9) Vector(1, 3, 4, 5, 9) Vector(1, 3, 9) Vector(1, 4, 5, 9) Some(7) Some(2) Some(8)
Vector(3, 7) Vector(3, 4, 6) Some(5) Vector(1, 3) Some(8) Some(2) Some(9) Vector(3, 4, 6, 7) Vector(1, 3, 4)
Some(2) Some(1) Vector(3, 4, 9) Some(7) Vector(3, 9) Some(6) Vector(3, 4, 5) Some(8) Vector(3, 4, 5)
Vector(3, 7) Vector(3, 6, 9) Some(8) Vector(1, 3, 5, 9) Some(4) Vector(1, 5, 9) Some(2) Vector(3, 6, 7) Vector(1, 3, 5)
Some(8) Some(3) Some(6) Vector(1, 4, 9) Some(7) Vector(1, 4, 9) Some(5) Vector(3, 4) Some(2)
Some(1) Some(5) Some(4) Some(6) Some(2) Some(3) Some(8) Some(9) Some(7)
Some(9) Some(2) Some(7) Vector(4, 8) Some(5) Vector(4, 8) Some(3) Some(1) Some(6)

Some(4) Some(7) Some(2) Some(3) Some(6) Some(8) Some(1) Some(5) Some(9)
Some(5) Some(8) Vector(1, 3, 9) Some(2) Vector(1, 9) Some(7) Some(6) Vector(3, 4) Vector(3, 4)
Some(6) Some(9) Some(3) Vector(1, 4, 5, 9) Vector(1, 9) Vector(1, 4, 5, 9) Some(7) Some(2) Some(8)
Vector(3, 7) Some(4) Some(5) Some(1) Some(8) Some(2) Some(9) Vector(3, 4, 6, 7) Vector(1, 3, 4)
Some(2) Some(1) Vector(3, 9) Some(7) Some(3) Some(6) Some(4) Some(8) Some(5)
Vector(3, 7) Vector(6, 9) Some(8) Vector(1, 5, 9) Some(4) Vector(1, 5, 9) Some(2) Vector(3, 6, 7) Vector(1, 3, 5)
Some(8) Some(3) Some(6) Vector(1, 4, 9) Some(7) Vector(1, 4, 9) Some(5) Some(4) Some(2)
Some(1) Some(5) Some(4) Some(6) Some(2) Some(3) Some(8) Some(9) Some(7)
Some(9) Some(2) Some(7) Some(8) Some(5) Some(4) Some(3) Some(1) Some(6)

Some(4) Some(7) Some(2) Some(3) Some(6) Some(8) Some(1) Some(5) Some(9)
Some(5) Some(8) Some(1) Some(2) Some(9) Some(7) Some(6) Some(3) Some(4)
Some(6) Some(9) Some(3) Some(4) Some(1) Vector(1, 5) Some(7) Some(2) Some(8)
Vector(3, 7) Some(4) Some(5) Some(1) Some(8) Some(2) Some(9) Some(6) Some(3)
Some(2) Some(1) Some(9) Some(7) Some(3) Some(6) Some(4) Some(8) Some(5)
Vector(3, 7) Some(6) Some(8) Vector(5, 9) Some(4) Vector(5, 9) Some(2) Vector(3, 6, 7) Some(1)
Some(8) Some(3) Some(6) Some(9) Some(7) Some(1) Some(5) Some(4) Some(2)
Some(1) Some(5) Some(4) Some(6) Some(2) Some(3) Some(8) Some(9) Some(7)
Some(9) Some(2) Some(7) Some(8) Some(5) Some(4) Some(3) Some(1) Some(6)

Some(4) Some(7) Some(2) Some(3) Some(6) Some(8) Some(1) Some(5) Some(9)
Some(5) Some(8) Some(1) Some(2) Some(9) Some(7) Some(6) Some(3) Some(4)
Some(6) Some(9) Some(3) Some(4) Some(1) Some(5) Some(7) Some(2) Some(8)
Some(7) Some(4) Some(5) Some(1) Some(8) Some(2) Some(9) Some(6) Some(3)
Some(2) Some(1) Some(9) Some(7) Some(3) Some(6) Some(4) Some(8) Some(5)
Some(3) Some(6) Some(8) Some(5) Some(4) Some(9) Some(2) Some(7) Some(1)
Some(8) Some(3) Some(6) Some(9) Some(7) Some(1) Some(5) Some(4) Some(2)
Some(1) Some(5) Some(4) Some(6) Some(2) Some(3) Some(8) Some(9) Some(7)
Some(9) Some(2) Some(7) Some(8) Some(5) Some(4) Some(3) Some(1) Some(6)

solved```

This is able to solve more difficult sudoku puzzles.

### aplicative composition

To quote Gibbons and Oliveira:

Monads have long been acknowledged as a good abstraction for modularising certain aspects of programs. However, composing monads is known to be difficult, limiting their usefulness. One solution is to use monad transformers, but this requires programs to be designed initially with monad transformers in mind. Applicative functors have a richer algebra of composition operators, which can often replace the use of monad transformers.

`Func` that is currently available in Scalaz 7.0.0-M4 introduces such composition operators. `@&&&` and `::` operator compose applicative functions in parallel (also known as product), while `@>>>` operator composes applicative functions in sequence. These compositions return applicative functions, which in turn could also be part of further compositions.

All `Monad`s are applicative. Any `Monoid` can also be treated as a monoidal applicative. (Zipping together Naperian data structure gives applicative too, but I haven't seen one.) When dealing with multiple instances of monads, keeping each context straight in your head can get complicated. Applicative compositions can be used to reason about them, especially combined with the mighty `traverse` method. For example, the following composes three applicative functions in parallel and returns a single `HListFunc`.

```  def evalMachine(pos: (Int, Int), n: Int) =
horizEvalMachine(pos) :: vertEvalMachine(pos) :: groupEvalMachine(pos, n) :: AppFunc.HNil```

Next by calling `evalMachine((3, 1), game.sqrtn) traverse cellsWithCs` in a single traversal over `cellsWithCs` it produces an hlist of state monads:

```scala> Solver.evalMachine((3, 1), game.sqrtn) traverse cellsWithCs
res1: scalaz.typelevel.TCCons[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.typelevel.TCCons[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.typelevel.TCCons[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.typelevel.TCNil]]]#Product[scala.collection.immutable.Vector[Unit]] = GenericCons(scalaz.StateT\$\$anon\$7@273cf345,GenericCons(scalaz.StateT\$\$anon\$7@12874b23,GenericCons(scalaz.StateT\$\$anon\$7@7055f055,GenericNil())))```

It's as if each evaluation machine traversed `cellsWithCs` independently. Since all three elements contain the same type, I can convert it into a plain list:

```scala> homogenize(res1)
res2: List[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M[scala.collection.immutable.Vector[Unit]]] = List(scalaz.StateT\$\$anon\$7@273cf345, scalaz.StateT\$\$anon\$7@12874b23, scalaz.StateT\$\$anon\$7@7055f055)```

From here we can simply evaluate the state monad individually to get the evaluations, or call `sequence` to turn the list of monads into a monad of list. What's important is how modular individual machines are. Since they are expected to run independently, they can focus on a few simple tasks.

### future works

With the current implementation, I could not find how to generate `HListFunc` from other sources like a list. This is due to the fact that each `HListFunc` has a unique type depending on the item that it stores. HList works around this issue by providing the common `HList` trait. Perhaps `HListFunc` should be implicitly convertible to `Func` instead of directly extending it.

Another area worth looking into is asynchronous processing of the functions. The parallel composition we've discussed so far are parallel in semantics, but the actual processing has been done sequentially. By combining something like the abstract future, it might be possible to distribute load off to other cores.