Thinking Functionally with Haskell勉強メモ: 第５章１ 数独ソルバー最適化以前
第５章は数独ソルバーの実装を通してHaskell/関数型プログラムの書き方（の一つ）を紹介するというもの。
まずは問題をできるだけ宣言的に解くコードを記述して、その後最適化していく。
この記事は第一段階の非常に非効率な宣言的コードの説明まで。
データ型の定義
まずは問題の入力と出力を表すデータ構造を型として定義する：
data Matrix a = [Row a] data Row a = [a] type Grid = Matrix Digit type Digit = Char digits :: [Digit] digits = ['1' .. '9'] blank :: Digit -> Bool blank = (=='0')
Matrix型は[[a]]のalias。一枚の数独問題（回答前・後を問わず）はGrid型で表現する。GridはMatrix Digitのaliasであり、DigitはCharのalias。記入されていないマスは0で表される。
solve関数
solve :: Grid -> [Grid] solve = filter valid . completions valid :: Grid -> Bool completions :: Grid -> [Grid]
数独を解く関数solveの定義。
問題をGridとして受け取り、正解回答となるGridすべてのリストを返す。completionsとvalidという二つの関数を組み合わせて作る。
まずはcompletions。問題Gridを受け取り、、空のマスに1から9までを当てはめていくことで問題を（間違っていてもいいので）埋めきったすべての（非常に多くの）パターンのGridのリストを返す。
validは埋めきったGridが数独のルールに従っているかを判定する。validでフィルタすることで、すべてのパターンから正解例のみを取り出す。
completions
定義は：
completions = expand . choices
構成要素である二つの関数の型は：
choices :: Grid -> Matrix [Digits] expand :: Matrix [Digits] -> [Grid]
あるいはこちらのほうがわかりやすいかもしれない：
choices :: Matrix Digits -> Matrix [Digits] expand :: Matrix [Digits] -> [Matrix Digits]
choicesはDigitsのMatrixである問題文から、確定しているマスは要素数１、空のマスは要素数９（1..9)のDigitsのリストのMatrixに変換する。
expandはその「各マスが取り得るDigit値を列挙したリストのMatrix」を引数にとり、「各マスの取り得る値の直積集合である『DigitのMatrixのリスト』」を返す。
choices
choices = map (map choice) choice d | blank d = digits | otherwise = [d]
個別のマスに対して、'0'以外ならその値のみ入っているリスト、'0'なら['1'..'9']を返すchoice関数を適用する。
例えば引数が
[['1', '2', '3', '4', '5', '6', '7', '0', '0'], ..., ......]
だった場合、以下を返す：
[[['1'], ['2'], ['3'], ['4'], ['5'], ['6'], ['7'], ['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['1', '2', '3', '4', '5', '6', '7', '8', '9']], ..., ......]
expand
expandを定義するためにはまずcp関数を定義する。cpとは直積集合Cartesian Productの略。定義は：
cp :: [[a]] -> [[a]] cp [] = [[]] cp (xs:xss) = [x:ys | x <- xs, ys <- yss] where yss = cp xss
例えばcpの引数が
[['1'], ['2'], ['3'], ['4'], ['5'], ['6'], ['7'], ['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['1', '2', '3', '4', '5', '6', '7', '8', '9']]
だった場合、以下を返す：
[['1', '2', '3', '4', '5', '6', '7', '1', '1'], ['1', '2', '3', '4', '5', '6', '7', '1', '2'], ['1', '2', '3', '4', '5', '6', '7', '1', '3'], ['1', '2', '3', '4', '5', '6', '7', '1', '4'], ... ['1', '2', '3', '4', '5', '6', '7', '9', '8'], ['1', '2', '3', '4', '5', '6', '7', '9', '9'], ]
map cpで一つ一つの行を「その行が取り得るすべての「９つのDigitのリスト」のリスト」に変換する。
それをさらにcpすることで、各行が取り得るすべての値の直積に変換する。それがマスを埋めたGridのパターンすべてを網羅したリストだ。
なのでexpandの定義は：
expand = cp . map cp
なのでcompletionsを展開していくと：
completions = expand . choices = cp . map cp . choices = cp . map cp . map (map choice)
となる。
valid
数独のルールに従ってvalidの定義は以下の通りになる：
valid g = all nodups (rows g) && all nodups (cols g) && all nodups (boxs g)
nodupsはno duplicatesの略。各行(rows)、各列(cols)、各3x3の区切り(boxs)にダブった数字がないことが正解の条件である。
all
all関数はリストのすべてがpを満たしているかチェックする：
all :: (a -> Bool) -> [a] -> Bool all p = and . map p
nodups
あるリストに同じ要素が二回出てくるかチェックする関数。
nodups :: (Eq a) => [a] -> Bool nodups [] = True nodups (x:xs) = all (/=x) xs && nodups xs
一見O(n2)だがn=9なので気にしない。
rows
rowsはあるGridの行のリストを返す関数。
本には型はrows :: Matrix a -> Matrix aとあったが、個人的には意味的にrows :: Matrix a -> [[a]]ではないか？と思っている。
たまたまMatrix aは[Row a]なのでrowの定義は：
row = id
cols
colsはGridの列のリストを返す関数。
これと次のboxsはどう考えてもMatrix a -> Matrix aというよりMatrix a -> [[a]]じゃないか？
cols = transpose transpose :: [[a]] -> [[a]] transpose [xs] = [ [x] | x <- xs] transpose (xs:xss) = zipWith (:) xs (transpose xss)
transposeは私が定義した。本の中ではtranspose関数はなく、直接colsをこの定義にしていた。ただ、colsという名前で書くのは（とくに次のboxsでも使う手前）不適当な気がしたのでいったんtransposeという名前で定義してcolsをaliasとした。
しかしこのtransposeの定義、一番最後のリストを一要素ずつのリストのリストにする、というのを再帰の終了条件にして、そのリストにzipWithで前のリストの要素を付け加えていく。理屈はわかるのだが自前で考えろと言われて書ける気が全くしない・・・
boxs
boxsは3マスx3マスの各区切りの中の数リストが９つ入ったリストを返す。
boxs :: Matrix a -> [[a]] boxs = map ungroup . ungroup . map transpose . group . map group group :: [a] -> [[a]] group [] = [] group xs = take 3 xs : group drop 3 xs ungroup :: [[a]] -> [a] ungroup = concat
リストを「3つの要素ごとのリスト」のリストに変換する関数がgroup、それを元のリストに戻すのがungroup（実際の処理はただのconcat）。
挙動を理解するのがけっこうややこしい関数の組み合わせなので、4x4のMatrixを2x2の区切り内の要素のリストに変換する様を書いてみる。
まず入力：
[[a1, a2, a3, a4], [b1, b2, b3, b4], [c1, c2, c3, c4], [d1, d2, d3, d4]]
map group適用：
[[[a1, a2], [a3, a4]], [[b1, b2], [b3, b4]], [[c1, c2], [c3, c4]], [[d1, d2], [d3, d4]]]
中の４つの要素のリストが、２つの要素のリスト二つのリストに変換されている。
次はgroup適用：
[[[[a1, a2], [a3, a4]], [[b1, b2], [b3, b4]]], [[[c1, c2], [c3, c4]], [[d1, d2], [d3, d4]]]]
4x2x2要素のリストのリストのリストだったのが、2x2x2x2のリストx4になっている。
map transpose：
[[[[a1, a2], [b1, b2]], [[a3, a4], [b3, b4]]], [[[c1, c2], [d1, d2]], [[c3, c4], [d3, d4]]]]
[a3, a4]と[b1, b2]、[c3, c4]と[d1, d2]の位置が入れ替わった。
ungroup適用：
[[[a1, a2], [b1, b2]], [[a3, a4], [b3, b4]], [[c1, c2], [d1, d2]], [[c3, c4], [d3, d4]]]
2x2x2x2から4x2x2に。
map ungroup適用：
[[a1, a2, b1, b2], [a3, a4, b3, b4], [c1, c2, d1, d2], [c3, c4, d3, d4]]
4x4のリストのリストに戻っているが、最初のリストはa1, a2, b1, b2と左上にあった数字、次のリストは右上、次は左下、最後は右下、と2x2に分割した各区切りの数字のリスト４つになっていることがわかる。
これを3x3の区切りで9x9のGridに適用したのが上記のboxs。
結論
rowsもcolsもboxsもすべてのリストがvalidならそのGridは数独のルール上正しく記入されていることになる。なのでcompletionsの戻り値をvalidでフィルタすれば、正しい回答のリストが得られる。
が、completionsが返すリストは遅延評価とはいえ981-k （kは数字が知られているマスの数）もの結果を返し、それを一つ一つフィルタしていかなければいけない。現実的に不可能である。
なので次回はこの非常に効率の悪いコードに対しどのような等価な変換を加えていくことで最適化ができるか、というポイントを探っていく。
