Sudoku validator

Question

I've decided to learn some more Haskell writing a Sudoku validator, the function checkSudoku outputs True if the Sudoku is valid and False if it is not. I did not write the checkSquares function because it would have been too hard. I am looking for any tip about Haskell and functional programming.

Some specific questions:

• Why is the Unit-test module so verbose?
• I did not use the type signatures because they would restrict my functions to work only on a certain type, while I may want to create sudokus of other types. Is it possible (and recommended?) to use poly-type type signatures?

import Test.HUnit
import Data.List
sudokuSize = 9
headLastRange sequence = [(head sequence) .. (last sequence)]
testHeadLastRange = TestCase $ assertEqual "" [1,2,3,4,5] (headLastRange [1,4,6,7,5])
findMissing sequence = filter (\x -> not (x `elem` sequence)) (headLastRange sequence)
testFindMissing = TestCase $ assertEqual "" [3,8] (findMissing [1,2,4,5,6,7,9])
findMissingMinMax min max sequence = filter (\x -> not (x `elem` sequence)) [min..max]
testFindMissingMinMax = TestCase $ assertEqual "" [1,2,5,8] (findMissingMinMax 1 10 [3,4,6,7,9,10])
nothingMissingSudoku sequence = (findMissingMinMax 1 sudokuSize sequence) == []
testNothingMissingSudoku = TestCase $ assertEqual "" True (nothingMissingSudoku [1..9])
occurencies item sequence = length (filter (\i -> i == item) sequence) 
testOccurencies = TestCase $ assertEqual "" 3 (occurencies 1 [1,2,3,5,5,1,4,6,1])
onlyOnce item sequence = (occurencies item sequence == 1)
testOnlyOnce = TestCase $ assertEqual "" True (onlyOnce 5 [1..10])
howManyOnlyOnce sequence = length (filter (\i -> onlyOnce i sequence) sequence)
eachOnlyOnce sequence = howManyOnlyOnce sequence == (length sequence)
testEachOnlyOnce = TestCase $ assertEqual "" True (eachOnlyOnce [4,6,8,2,1])
getLines sudoku = sudoku -- syntactic sugar, the sudoku is already a list of lines.
checkLines sudoku = (all nothingMissingSudoku (getLines sudoku)) && (all eachOnlyOnce (getLines sudoku))
testCheckLines = TestCase $ assertEqual "" True (checkLines [[1..sudokuSize],[1..sudokuSize]])
rotateClockWise sudoku = map reverse . transpose $ sudoku
testRotateClockWise = TestCase $ assertEqual "" [[1,1],[2,2]] (rotateClockWise [[1,2],[1,2]])
getColumns sudoku = rotateClockWise sudoku
checkColumns sudoku = all nothingMissingSudoku (getColumns sudoku) && (all eachOnlyOnce (getColumns sudoku))
columnsCorrectSize sudoku = all (==sudokuSize) (map length sudoku)
checkSize sudoku = (length sudoku) == sudokuSize && columnsCorrectSize sudoku
-- TODO: add check for 3x3 squares
checkSudoku sudoku = checkSize sudoku && checkColumns sudoku && checkLines sudoku
testCheckSudoku = TestCase $ assertEqual "" True (checkSudoku [[5,3,4,6,7,8,9,1,2],
 [6,7,2,1,9,5,3,4,8],
 [1,9,8,3,4,2,5,6,7],
 [8,5,9,7,6,1,4,2,3],
 [4,2,6,8,5,3,7,9,1],
 [7,1,3,9,2,4,8,5,6],
 [9,6,1,5,3,7,2,8,4],
 [2,8,7,4,1,9,6,3,5],
 [3,4,5,2,8,6,1,7,9]])
allTests = [testHeadLastRange, testFindMissing, testOccurencies, testOnlyOnce, 
 testEachOnlyOnce, testNothingMissingSudoku, testFindMissingMinMax, testCheckLines,
 testRotateClockWise, testCheckSudoku]
main = runTestTT $ TestList allTests

• bisserlis: Check out Graham Hutton's Sudoku solver functional pearl for a complete solution. It's pretty mind-blowing.

Answer 1

Why is the Unit-test module so verbose?

This isn't a code review question, but I don't think it's particularly verbose. It's certainly no worse than JUnit looks to my eyes.

I did not use the type signatures because they would restrict my functions to work only on a certain type, while I may want to create sudokus of other types. Is it possible (and recommended?) to use poly-type type signatures?

This isn't a valid reason not to use type signatures. If you want to save yourself some keystrokes on type signatures when you change a representation, then you should be using a type alias instead.

type Row a = [a]
type Matrix a = [Row a]

Then if you were to switch from using lists to e.g. Vectors,

type Row a = Vector a
type Matrix a = Vector (Row a)

This also pushes the site of compiler errors from where you're calling the function to the body of the function you're calling if you forget to change all of your imports or implementations.

It also makes it immediately clear whether a function is working on an individual row or the whole puzzle or what.

---

You use lambdas where you can get away with function sections. E.g.,

(\x -> not (x `elem` sequence))
-- equivalent to
(`notElem` sequence)

findMissingMinMax is equivalent to list difference with a range.

findMissingMinMax min max sequence = [min..max] \\ sequence

In testCheckSudoku you can use assertBool instead of assertEqual.

findMissing and headLastRange look to be dead code.

You recognized that columns are just rotated rows, but then still duplicate a bunch of code to check them instead of reusing the checkLines function. I.e.,

checkColumns = checkLines . rotateClockWise

You have some logic/naming misconceptions in places. For instance, columnsCorrectSize is really checking that your rows/lines are the correct length.

getLines isn't syntactic sugar, it's a no-op. Its implementation should be getLines = id, because what's really interesting about it should be the type.

getLines :: Matrix a -> [Row a]
getLines = id

Even though Matrix a and [Row a] refer to the same normalized type, it signals a conceptual difference in how the value should be treated.