2026-09-08
Assign.hs
type Clause = [Int]
assign :: Int -> [Clause] -> [Clause]
assign l = map (filter (/= negate l)) . filter (notElem l)
main :: IO ()
main = do
let cs = [[1, -2], [2, 3], [-1, -3]]
print (assign 1 cs)
print (assign -2 cs)
SATソルバの部品で、リテラル l を真にしたときに節のリストを簡約する assign です。節は整数のリストで、k は k 番目の変数 xk が真、-k は偽を表します。l を含む節は満たされたので取り除き、残りの節からは l の否定を消します。main では、節のリスト cs に対して x1 を真にした結果と、x2 を偽にした結果を出力するつもりです。本来は [[2,3],[-3]] と [[3],[-1,-3]] の2行を出力しますが、いまはコンパイルが通りません。どこを直せばよいでしょうか?
Answer
print (assign -2 cs) を print (assign (-2) cs) に変えます。
Haskell の - は、式の先頭にあれば符号の反転ですが、関数の引数の位置に置くと二項演算子の引き算として読まれます。関数適用は引き算より強く結びつくので、assign -2 cs は assign - (2 cs) と同じで、関数 assign から 2 cs を引く式になります。関数どうしの引き算も、数値 2 を関数として cs に適用することも型が合わず、コンパイルエラーになります。
丸括弧で (-2) とまとめれば、括弧の中では - が式の先頭にあるので符号の反転として読まれ、-2 という1つの引数になります。assign (-2) cs は -2 を含む [1, -2] を取り除き、残りの節から 2 を消して [[3],[-1,-3]] を返します。1行目の assign 1 cs は正の数なので、括弧がなくても問題ありません。