Cheat sheet ...

[jrp2014]

This is a great package that I am trying to use to write a Soduko solver using Conor McBride's types:

   20 type Triple = Id :*: Id :*: Id 
   21  
   22 pattern Tr :: a -> a -> a -> (:*:) (Id :*: Id) Id a 
   23  
   24 pattern Tr a b c = (Id a :*: Id b) :*: Id c 
   25  
   26 type Row = Triple :. Triple 
   27  
   28 type Grid = Matrix Value 
   29  
   30 type Matrix = Row :. Row 
   31  
   32 type Value = Char 
   33  
   34 type Choices = [Value] 

rather than lists + indexes.

Everything is easy, using functor-combo's Functor until I get to trying to implement a version of the Bird expand / expand1 functions, which use pattern matching for elegant simplicity. For these I think that I need holes / derivatives (to test candidate solutions for a cell, aka guessing). There seem to be two implementations of these concepts in functor-combo (DHoley, Derivative + Holey). Which should I be using? Similarly, I assume that I will need some sort of Zipper, but it isn't obvious how to create these from the modules. For example, in the ZipperFix case, Fix is not accessible to the user.

It would be helpful to expand the documentation to cover use cases (the blog is helpful for concepts / implementation of the package).

Many thanks!

[conal]

Everything is easy, using functor-combo's Functor until I get to trying to implement a version of the Bird expand / expand1 functions, which use pattern matching for elegant simplicity.

Do you have a pointer to these functions? I just looked in Richard Bird's Soduko paper but didn't spot them.

I made the functor-combo package to support some experiments and blog posts, but now there's GHC.Generics. It may be worthwhile to port some functionality from functor-combo and then abandon it.

[jrp2014]

Hi Conal,

Here is Graham Hutton's rendering of the Bird approach: http://www.cs.nott.ac.uk/~pszgmh/sudoku.lhs

It can be refactored to use the types above quite easily, although there are some interesting cases, such as checking for duplicates.

The expand function is:

> expand                :: Matrix Choices -> [Matrix Choices]
> expand m              =
>    [rows1 ++ [row1 ++ [c] : row2] ++ rows2 | c <- cs]
>    where
>       (rows1,row:rows2) = break (any (not . single)) m
>       (row1,cs:row2)    = break (not . single) row

This can be further optimized to

expand1 :: Matrix Choices → [Matrix Choices]
expand1 rows = [rows1 ++ [row1 + [c] : row2] ++ rows2 | c ← cs]
  where( rows1,row:rows2) = break(any smallest) rows
             (row1,cs : row2)  = break smallest row
             smallest cs          = length cs ==  n
             n                           = minimum (counts rows) 
counts = filter (/= 1) · map length · concat

expand = concat · map expand · expand 1

The initial parts of the problem illustrate the power and elegance of foldable / traversable / applicative, but a different model is needed when you need to do more than apply the same effect uniformly across the grid.

A further refinement uses a generalisation of the approach of pruning pairs used here. It is described here https://wiki.haskell.org/Sudoku/Thorkil_Naur. Links to an implementation of this approach can be found at https://wiki.haskell.org/Sudoku under the Generalized Solver section.

I have found this a good exercise because the problem is well-known and there are lots of model Haskell solutions around. But most of them use lists and / or indexes (which is fine, but it feels a bit hand-crafted). nextGrids here https://abhinavsarkar.net/posts/fast-sudoku-solver-in-haskell-1/ is another version of expand1 that illustrates the point. I feel that it ought to be possible to use Conor's Triple type as the basis of a more satisfying approach (or use it to provide insights into the limitations of the approach).

I'll have a look at GHC.Generics more closely. I didn't spot the plumbing for holes and derivatives, the last time I looked (for other purposes).