Sudoku Solver in Scala Part 2: Functions compose, methods don't

I keep writing about my learnings during writing a sudoku solver. This time we touch solver's logic and I have something to share about making the big functions out of the small ones.

Previous part: Injecting validation into the type system.

Algorithm

Simple solver algorithm looks like this:

  1. In every box search for values that can be filled only in single place. Fill them.
  2. Repeat same logic for every row.
  3. Repeat same logic for every column.
  4. Fill empty cells where only single value is allowed.
  5. Repeat these steps while they are producing new results.

If this is not enough we do something like depth-first search.

  1. Find an empty cell.
  2. Fill it with any allowed value.
  3. Try solving the sudoku we've got.
    • If we could solve it - that's our solution.
    • If we produced an unsolvable sudoku - we know this value can't be at that place.

With this second layer logic we can solve even empty sudokus.

It took a while to define "unsolvable sudoku" in source code terms. It's a grid containing an empty cell with an empty set of allowed values.

Composing methods

Different books write that in functional programming we tend to split data and logic my making dumb data structures and writing logic in pure functions outside. This sounds good on paper but in practice I started writing classes as I used to. I did it wrong. But the interesting part is it was proven wring not by someone else but by code itself.

It all started with me writing fillBox method for Grid class. It checks for digits that can be filled only in one place in a box and fills them. Return value is either a grid with filled digits or this grid if we found nothing.

class Grid(val body: Vector[Cell]) {
    def fillBox(box: Digit): Grid = ???
}

Looks good so far. What's next?

Next thing we want is a function that tries to fill every box. So we want to run this.fillBox(1).fillBox(2)... and so on. Can we do it without copypasting fillBox 9 times? Yes, with foldLeft function.

class Grid(val body: Vector[Cell]) {
    def fillBox(box: Digit): Grid = ???
    def fillBoxes: Digit = (1 to 9).foldLeft(this)((grid, box) => grid.fillBox(box))
}

This function doesn't look so good. I don't like the fact that it knows that class Grid has method fillBox and we need to create lambdas to wrap this knowledge into a function something else can consume.

So I refactored fillBox in order to make fillBoxes look better.

I moved it away from class to be a function, remembering the phrase from this great talk: "methods are hard to compose, functions are composable out of the box".

But to make it composable I had to do that one thing I never understood. I swapped the arguments order.

Not sure if it's documented somewhere but usually in OOP you order function arguments is some specific way: first you define what you want to process in a function (input), then you define how (function-specific parameters). In functional world function-specific parameters go first and even (in Scala case) as a different set of arguments to make currying easier.

This makes sense. A function that accepts parameters is quite generic and with this approach you can easily convert it to a more specific function to be used somewhere else. This is even more important in functional approach because you are using all those higher order functions that expect specific functions as input.

After refactoring my code looks somehow like this.

class Grid(val body: Vector[Cell]) {}
object Grid {
    def fillBox(box: Digit)(grid: Grid): Grid = ???
    def fillBoxes: Grid => Grid = (1 to 9).map(fillBox).reduce(_ compose _)
}

Now fillBoxes doesn't need to know anything about Grid class internals. It just composes functions. It knows about fillBox but that's not required. It can compose anything if you provide it a Digit => A => A function as input.

And that's what I did later after creating fillCol(col: Digit)(grid: Grid): Grid and fillRow(row: Digit)(grid: Grid): Grid functions.

object Solvers {
  private type BasicSolver = Grid => Grid;

  private def forEveryDigit(f: Digit => BasicSolver): BasicSolver =
    (1 to 9).map(f).reduce(_ compose _)
}

Making basic solvers a function gave me easy ways to combine them into more powerful solvers without having to write any grid-specific code.

Summary

For me it's the biggest paradigm shift for now. In OOP you're discouraged to write just functions or static class methods. You should write usual methods because you can't override a function so you cannot mock it in tests. In functional programming you are discouraged to write methods because it's hard to compose them. You need to write functions instead. You still can't mock them but it's not a problem anymore because your functions are pure and you don't need to mock dependencies that have no side effects.

Next time I'll write about generating cross-dependent data for property tests.

Tags: , ,


Comments