Namaran

Code daily. Without assist.

2026-09-09

Counterexample.hs

import Control.Monad (replicateM)
import Data.List (find, sort)

small :: [[Int]]
small = concatMap (`replicateM` [1, 2]) [0 .. 2]

check :: String -> ([Int] -> [Int] -> Bool) -> IO ()
check name prop =
  putStrLn (name ++ ": " ++ maybe "ok" show (find (not . uncurry prop) cases))
  where
    cases = [(xs, ys) | xs <- small, ys <- small]

main :: IO ()
main = do
  check "reverse" (\xs ys -> reverse (xs ++ ys) == reverse xs ++ reverse ys)
  check "sort" (\xs ys -> sort (xs ++ ys) == sort xs ++ sort ys)
  check "length" (\xs ys -> length (xs ++ ys) == length xs + length ys)

これは何を出力するでしょうか?

Answer

reverse: ([1],[2])、sort: ([2],[1])、length: ok の3行を出力します。

replicateM n [1, 2] は、リストモナドで [1, 2] から n 回選んだ組み合わせを、左の位置ほどゆっくり変わる順に並べます。これを長さ0、1、2の順につなぐので、small は [[], [1], [2], [1,1], [1,2], [2,1], [2,2]] です。cases の内包表記では右側の生成器 ys のほうが速く回り、xs を固定したまま ys を一巡してから次の xs へ進みます。find は性質が破れた最初の組を返し、それより後ろの組は評価しません。

reverse の性質は、xs が空なら常に成り立ちます。xs = [1] でも ys が [] と [1] のうちは成り立ち、ys = [2] で左辺の reverse [1,2] が [2,1]、右辺が [1,2] になって初めて破れます。sort の性質は、xs = [1] の7通りでは 1 がどの要素よりも大きくないので、右辺の [1] ++ sort ys も昇順になってすべて成り立ちます。次の xs = [2] で、ys = [1] のとき左辺が [1,2]、右辺が [2,1] に分かれます。length の性質はどの組でも成り立つので、find は Nothing を返し、ok が出ます。

小さい入力から順に総当たりして最初の反例を返すと、見つかる反例はその並びの中で最小のものになります。Haskellのライブラリでは SmallCheck がこの方式で、QuickCheck はランダムな入力で反例を見つけたあと、縮小(shrinking)で小さい反例へ近づけます。