Haskell初級者がAtCoderの問題でプロパティベーステストを試す
はじめに
『実践プロパティベーステスト』のおかげか、最近プロパティベーステストが流行ってますね！
この記事は、Haskell初級者の僕がAtCoderの問題を元にHaskellでプロパティベーステストを試してみる記事です。
まだまだプロパティベーステスト勉強はじめたばかりなので(まだ第一部しか読んでない)、おかしいところがあれば優しく指摘いただけるととても嬉しいです！
プロパティベーステストって何？
簡単に説明すると、以下の様な感じになります。
- どのような入力値を与え ても常に同じであるような振る舞いをテストする(この実行可能なコードがプロパティ)と言っている(普通のユニットテストのことを事例ベーステストと言っている)
- ジェネレータ(特定の型を表すメタデータ)を元にフレームワークがテストデータを生成する
これにより、一般的なユニットテストでよくやる『テストデータを期待値を一つ一つ用意してin/outをテストする』必要がなくなるので、 テストコードの行数を減らせたり、従来のテストでは見つけづらかったバグを見つけることが可能になるというメリットがあります。
ただ、この『どうプロパティを書いていけばいいの？』というのはなかなか難しく、「実践プロパティベーステスト」にもはっきりと「習得するには訓練が必要」と書いてあります。
何をするの？
実践プロパティーベステストやHaskellのQuickCheck、こちらの記事を参考にAtCoderの問題にQuickCheckを試してみて、どんな感じになるか感覚を掴んでいきたいと思います！
今回題材にするのはこちらの問題です。
この問題の内容は以下の通り、レピュニットと言われる全て1桁の数を足した和のうちN番目に小さいものを求める問題です。
[問題文]
十進法ですべての桁の数字が
1 である整数をレピュニットと呼びます。レピュニットを小さい順に並べると
1,11,111,… です。
ちょうど
3 つのレピュニットの和として表せる整数のうち
N 番目に小さいものを求めてください。
[制約]
N は
1 以上
333 以下の整数
プロパティベーステストを書いてみる
この回答を以下のように書いたとします。
main :: IO ()
main = do
n <- readLn @Int
print $ nthRepunitSum n
-- レピュニットを生成する関数
repunits :: [Int]
repunits = map (\n -> read (replicate n '1')) [1 ..]
-- n番目のレピュニットの和を求める関数
nthRepunitSum :: Int -> Int
nthRepunitSum n = (map head . L.group . L.sort $ [x + y + z | x <- take 12 repunits, y <- take 12 repunits, z <- take 12 repunits]) !! (n - 1)
まずはQuickCheckを使える様にします。
僕は普段cabalを使っているので、 *.cabalにQuickCheckを追記します。
build-depends: base ^>=4.16.4.0,
QuickCheck
これに対するプロパティベーステストを書いていきましょう。
「実践プロパティベーステスト」には、プロパティを作る指針として以下をあげています。
- モデリング(より単純で明らかに正しい実装との比較)
- 従来の事例テストの汎用化(手作業でやっていたことの自動化)
- プログラムの不変値を見つける
- 対称的な性質を利用する
今回の場合、1と3はできそうですが、2と4は難しそうです。
なので、1,3のプロパティベーステストを実装していきましょう。
まず『1. モデリング』ですが、パフォーマンスを気にせず、明確さと正確さを優先した基準実装を書きます。
実装例はこんな感じです。(ChatGPTに書いてもらいました)
-- レピュニットを生成する関数
repunit :: Int -> Integer
repunit n = read $ replicate n '1'
-- 3つのレピュニットの和のリストを生成する関数
repunitSums :: [Integer]
repunitSums = [x + y + z | x <- repunits, y <- repunits, z <- repunits]
where repunits = map repunit [1..12] -- 適切な上限までのレピュニットを生成
-- N番目のレピュニットの和を求める関数
nthRepunitSum :: Int -> Integer
nthRepunitSum n = sort (nub repunitSums) !! (n - 1)
次に、『3. プログラムの不変値を見つける』ですが、今回は全て正の値になるはずなので、このように書けます。
prop_positiveOutput :: Int -> Bool
prop_positiveOutput n = n > 0 && n <= 333 ==> nthRepunitSum n > 0
全体像をまとめるとこんな感じです。
import Test.QuickCheck
main :: IO ()
main = do
n <- readLn @Int
print $ nthRepunitSum n
-- レピュニットを生成する関数
repunits :: [Int]
repunits = map (\n -> read (replicate n '1')) [1 ..]
-- n番目のレピュニットの和を求める関数
nthRepunitSum :: Int -> Int
nthRepunitSum n = (map head . L.group . L.sort $ [x + y + z | x <- take 12 repunits, y <- take 12 repunits, z <- take 12 repunits]) !! (n - 1)
{- Property Base Test -}
-- モデリング
prop_matchSimpleImplementation :: Int -> Property
prop_matchSimpleImplementation n = n > 0 && n <= 333 ==> nthRepunitSum n == nthRepunitSumModel n
-- プログラムの不変値を見つける
prop_positiveOutput :: Int -> Property
prop_positiveOutput n = n > 0 && n <= 333 ==> nthRepunitSum n > 0
-- helper
-- レピュニットを生成する関数
repunitModel :: Int -> Int
repunitModel n = read $ replicate n '1'
-- 3つのレピュニットの和のリストを生成する関数
repunitSumsModel :: [Int]
repunitSumsModel = [x + y + z | x <- repunits, y <- repunits, z <- repunits]
where
repunits = map repunitModel [1 .. 12] -- 適切な上限までのレピュニットを生成
-- N番目のレピュニットの和を求める関数
nthRepunitSumModel :: Int -> Int
nthRepunitSumModel n = L.sort (L.nub repunitSumsModel) !! (n - 1)
実行するとこんな感じになります。
ghci> Test.QuickCheck.quickCheck prop_matchSimpleImplementation
+++ OK, passed 100 tests; 112 discarded.
ghci> Test.QuickCheck.quickCheck prop_positiveOutput
+++ OK, passed 100 tests; 120 discarded.
うまくいってそうですね！誤った実装だとどうなるか試してみましょう。
たとえば
-- n番目のレピュニットの和を求める関数
nthRepunitSum :: Int -> Int
nthRepunitSum n = (map head . L.group . L.sort $ [x - y - z | x <- take 12 repunits, y <- take 12 repunits, z <- take 12 repunits]) !! (n - 1)
として実行すると
- モデリングのテスト
ghci> Test.QuickCheck.quickCheck prop_matchSimpleImplementation
*** Failed! Falsified (after 1 test and 0.1 shrink *** Failed! Falsified (after 1 test):
1
- 不変値のテスト
ghci> Test.QuickCheck.quickCheck prop_positiveOutput
*** Failed! Falsified (after 1 test and 0.1 shrink *** Failed! Falsified (after 1 test):
1
と、どちらも失敗していることが確認できました！うまく使えてそうです。
まとめ
- プロパティベーステストは「どのような入力値を与えても常に同じであるような振る舞い」をテストする手法
- 以下の指針でテスト作ると良い
- モデリング(より単純で明らかに正しい実装との比較)
- 従来の事例テストの汎用化(手作業でやっていたことの自動化)
- プログラムの不変値を見つける
- 対称的な性質を利用する
- プロパティを作る方法がちょっとだけわかった
- 「実践プロパティベーステスト」は名著
これからやりたいこと
- 「実践プロパティベーステスト」をまず読破します。
- まだ全然使いこなせてないのでもっと使い込みたい
- 業務でも使えないか試してみたい
- ジェネレータもうまく使えるようになりたい
- AtCoderでうまく活用したい
まだまだ触りしか理解できていないので、もっと使いこなせるように頑張ります！
Discussion