Namaran

Code daily. Without assist.

2026-09-08

Propagate.hs

type Clause = [Int]

propagate :: [Clause] -> Maybe ([Int], [Clause])

節は整数のリストで、k は k 番目の変数が真、-k は偽を表すリテラルです。リテラルが1つだけの節(単位節)があれば、そのリテラルは真にするしかありません。単位節のうちリストの先頭に最も近いもののリテラルを真にし、それを含む節を取り除き、残りの節からその否定を消す、という手順を単位節がなくなるまで繰り返す propagate を書いてください。真にしたリテラルを順に並べたリストと、残った節を Just で返します。空の節が生じたら矛盾なので Nothing を返します。propagate [[1], [-1, 2], [-2, 3, 4]] → Just ([1,2],[[3,4]])、propagate [[1], [-1]] → Nothing、propagate [[1, 2]] → Just ([],[[1,2]])

Reference
propagate :: [Clause] -> Maybe ([Int], [Clause])
propagate cs
  | any null cs = Nothing
  | otherwise = case [l | [l] <- cs] of
      [] -> Just ([], cs)
      l : _ -> do
        (ls, rest) <- propagate (map (filter (/= negate l)) (filter (notElem l) cs))
        return (l : ls, rest)

参考実装は、まず any null cs で空の節を探します。空の節はリテラルが1つも残っていない節で、もう真にできないので Nothing です。次にリスト内包表記 [l | [l] <- cs] で単位節のリテラルを集めます。内包表記ではパターン [l] に合わない節が黙って読み飛ばされるので、要素が1つの節だけが残ります。

単位節がなければ、何も割り当てずに Just ([], cs) を返します。あれば先頭の l を真にして節を簡約し、その結果に対して propagate を呼び直します。[[1], [-1, 2], [-2, 3, 4]] では、1 を真にすると [-1, 2] が [2] に縮んで新しい単位節になり、呼び直した先で 2 が真になって [[3, 4]] が残ります。

再帰呼び出しは Maybe の do 記法の中にあるので、奥で矛盾して Nothing が返れば、それがそのまま全体の結果になります。Just が返ったときだけ、真にした l を先頭に付けて返します。[[1], [-1]] では 1 を真にした時点で [-1] が空の節になり、次の呼び出しの any null が Nothing を返します。

掲載したのは参考実装で、唯一の正解ではありません。Data.List の find で単位節を1つ探す形でも書けます。