2026-09-09
Check.hs
import Data.List (group, nub)
nextSeed :: Int -> Int
nextSeed s = (s * 1103515245 + 12345) `mod` 2147483648
randomList :: Int -> ([Int], Int)
randomList s = go (s `mod` 4) (nextSeed s)
where
go :: Int -> Int -> ([Int], Int)
go 0 t = ([], t)
go k t =
let (rest, t') = go (k - 1) (nextSeed t)
in (t `div` 65536 `mod` 3 : rest, t')
check :: Int -> Int -> ([Int] -> Bool) -> String
check 0 _ _ = "passed"
check n seed prop =
let (xs, seed') = randomList seed
in if prop xs then check (n - 1) seed prop else "failed: " ++ show xs
dedup :: [Int] -> [Int]
dedup xs = [x | (x : _) <- group xs]
main :: IO ()
main = putStrLn (check 100 42 (\xs -> dedup xs == nub xs))
check は、乱数で作ったリストを n 個、順に性質 prop に与え、すべて成り立てば "passed" を、成り立たないリストがあれば "failed: " に続けてそのリストを返すつもりの関数です。試している性質は、dedup が nub と同じ結果を返すことです。入力は main のとおり check 100 42 (\xs -> dedup xs == nub xs) です。いまの出力は passed ですが、本来の出力は failed: [1,0,1] です。どこを直せばよいでしょうか?
Answer
check の再帰呼び出しに渡す種を seed から seed' に直し、then check (n - 1) seed' prop にします。
Haskellの関数は同じ引数に対して同じ結果を返すので、randomList seed も同じ seed からは毎回同じリストを作ります。randomList は作ったリストと一緒に次の種 seed' を返しているのに、再帰呼び出しには元の seed を渡しているので、100回とも種42から作った [1,2] を試しています。[1,2] には重複がなく、dedup と nub の結果が一致するので passed になります。
seed' を渡すと回ごとに違うリストが作られ、3回目の [1,0,1] で dedup は [1,0,1]、nub は [1,0] を返して失敗します。group は隣り合う同じ値しかまとめないので、dedup は離れた重複を除けません。このバグはテストが落ちずに通ってしまうので、出力を見ても気づけません。-Wall を付けてコンパイルすると、使われていない seed' が警告されます。QuickCheck のようなライブラリは、乱数の生成器を Gen モナドの中に隠し、この受け渡しを利用者に書かせません。