は、Haskellで関数の候補を書く手助けが必要です

Question

こんにちはthisスレッドをこのスレッドを処理しています。 また、thisスレッドがintrestのものかもしれません。数独

data Sudoku = Sudoku { rows :: [[Maybe Int]] } 
deriving (Show, Eq) 

を与えられ、位置（type Pos = (Int, Int)） は、あなたが数独の行で、たとえば、そこに書くことができますどのような数字を決定する関数

candidates :: Sudoku -> Pos -> [Int] 

を書き込もうとし

イムすでに（1,2,4,7,9、x、x）が入っている場合は、最後の行にすでに存在する数字のいずれかを書き込めません。また、もう一つの問題は、hightとwidthをチェックして、何度も何度も数字が現れないようにすることです（通常のsudokuルール）。それでは、どのように始めるべきですか？

例： 数独>候補の一例（0,2） [4,8]

Answer 1

私は大学で私のアルゴリズムクラスでこのプロジェクトをやって覚えています。私の最善のアドバイスは、特に生産のためではなく、学習のためにハスケルに書いている人にとっては、「トップダウン」と書くことです。まず、この問題を解決するために何をする必要があるのでしょうか？それから、説明的な機能を使って書き留めてください（まだ存在していなくても）。次に、必要な機能をスタブします。例えば、開始は次のようになります。このことから

candidates :: Sudoku -> Pos -> [Int] 
candidates s p = union (rowCands s p) (colCands s p) (blockCands s p) 

rowCands :: Sudoku -> Pos -> [Int] 
rowCands = undefined 
colCands :: Sudoku -> Pos -> [Int] 
colCands = undefined 
blockCands :: Sudoku -> Pos -> [Int] 
blockCands = undefined 

あなたがすべてに答えてきたまで、あなたは単に、トップダウンrowCands問題を解決する方法を説明し始めるでしょう。 unionに似た関数を書こうと思うこともありますが、前にすでに書かれていることは確かです。 http://haskell.org/hoogleをチェックしてみてください。関数名や型名を検索することができます。おそらく、すでに標準ライブラリに書かれているunionがあるでしょうか？

自分で答えるのが面白い質問ですが、undefinedのタイプは何ですか？それはなぜタイプチェックですか？これは特別なキーワードではありません。それはあらかじめ定義された関数です。

Answer 2

ここにはData.Setを使用する解決策があります。 S.elemsを使ってリストを取得できますが、もしあなたがsudokuソルバを作っているのであれば、S.sizeを探しているかもしれません。

import qualified Data.Set as S 
import Data.Maybe(catMaybes) 

fullSet = S.fromAscList [1..9] 

fromJustL = S.fromList . concatMaybes 

candidates s x = 
    rowSet s x `S.intersection` colSet s x `S.intersection` cellSet s x 

rowSet s (i,_) = fullSet `S.difference` fromJustL (s !! i) 
colSet s (_,i) = fullSet `S.difference` fromJustL (map (!!i) s) 
cellSet s (i,j) = fullSet `S.difference` fromJustL (concatMap (g j) (g i s)) 
    where 
    g i | i < 3  = take 3 
     | i < 6  = take 3 . drop 3 
     | otherwise = take 3 . drop 6