QuickCheckを試してみる

フラワー

HaskellのQuickCheckを試してみる
参考にするのはこれ

題材はこれ

フラワー

実践プロパティベーステストのこれをテーマに実装すると良さそう(第三章プロパティで考えるより)

モデリング(より単純で明らかに正しい実装との比較)
従来の事例テストの汎用化(手作業でやっていたことの自動化)
プログラムの不変値を見つける
対称的な性質を利用する

フラワー

前提として、「実践プロパティベーステスト」は第一部しか読めていない

フラワー

まずプロパティベーステストとは何か？から

どのような入力値を与えても常に同じであるような振る舞いをテストする(この実行可能なコードがプロパティ)と言っている(普通のユニットテストのことを事例ベーステストと言っている)
ジェネレータ(特定の型を表すメタデータ)を元にフレームワークがテストデータを生成する

これによって、従来のユニットテストだと「テストデータを一つ一つ用意してテストしないといけない」という事をやる必要がなくなる。
そのためテストコードの行数を減らせたり、従来のテストでは見つけづらかったバグを見つけることができる？と思っている。

フラワー

ただ、プロパティベーステストはユニットテストの様な「あるinputに対して対応するoutputの整合性が取れていること」をテストするのではない。
テスト対象のコードそれ自体が持つ「性質（これをプロパティと呼んでいる）」をテストする必要がある。

QuickCheckだとこんな感じ。
これだとプロパティは(reverseしたものをreverseすると元の配列になる)となっている。

import Test.QuickCheck

prop_reverse :: [Int] -> Bool
prop_reverse xs = reverse (reverse xs) == xs

で、どうプロパティを書いていけばいいの？というのは難しくて、「実践プロパティベーステスト」はここを丁寧に解説している。

フラワー

最初に戻って、https://atcoder.jp/contests/abc333/tasks/abc333_c のプロパティベーステストを実装していく。この問題は以下の通り。

[問題文]
十進法ですべての桁の数字が 
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を使える様にする。これはHaskellのプロパティベーステストで使うフレームワーク。

自分はcabalを使っているので、.cabalファイルのbuild-depend:にこれを追記する。

build-depends:    base ^>=4.16.4.0,
                  QuickCheck

testsディレクトリを作成する。ディレクトリ構成はこんなイメージ(ChatGPTが作ってくれた)

myproject/
│
├── src/
│   ├── Main.hs          # メインアプリケーションコード
│   └── ...              # その他のソースファイル
│
├── test/
│   ├── TestMain.hs      # テストランナー
│   └── ...              # その他のテストファイル
│
├── myproject.cabal     # Cabalビルドファイル
└── ...

フラワー

実際に実装していく。まずはこれ

モデリング(より単純で明らかに正しい実装との比較)

ここで行うモデリングは、パフォーマンスを気にせず、明確さと正確さを優先する。
モデリングとなる実装を以下とする。(これも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)

フラワー

従来の事例テストの汎用化(手作業でやっていたことの自動化)

事例テストは、問題の入手力のサンプルを見ればわかる

入力例1
5
出力例1
113

入力例2
19
出力例2
2333

入力例3
333
出力例3
112222222233

今回は事例テストから汎用化が難しそうなのでパス

フラワー

プログラムの不変値を見つける
今回は全て正の値になるはずなので、こんな風に書ける

prop_positiveOutput :: Int -> Bool
prop_positiveOutput n = n > 0 && n <= 333 ==> nthRepunitSum n > 0

フラワー

対称的な性質を利用する
これはなさそうなのでパス

フラワー

まとめるとこう

module Main where

import Main (nthRepunitSum)
import Test.QuickCheck

-- モデリング
prop_matchSimpleImplementation :: Int -> Bool
prop_matchSimpleImplementation n = n > 0 && n <= 333 ==> nthRepunitSum n == repunitSumsModel n

-- プログラムの不変値を見つける
prop_positiveOutput :: Int -> Property
prop_positiveOutput n = n > 0 && n <= 333 ==> nthRepunitSum n > 0

-- helper
-- レピュニットを生成する関数
repunitModel :: Int -> Integer
repunitModel n = read $ replicate n '1'

-- 3つのレピュニットの和のリストを生成する関数
repunitSumsModel :: [Integer]
repunitSumsModel = [x + y + z | x <- repunitsModel, y <- repunitsModel, z <- repunitsModel]
  where
    repunits = map repunitModel [1 .. 12] -- 適切な上限までのレピュニットを生成

-- N番目のレピュニットの和を求める関数
nthRepunitSumModel :: Int -> Integer
nthRepunitSumModel n = sort (nub repunitSumsModel) !! (n - 1)

フラワー

うまく依存関係解決できなかったので、全部Main.hsに入れてやってみる（おい）
こんな感じ

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)

実行するとこう(https://blog.miz-ar.info/2020/08/debugging-with-quickcheck/ を参考にした)

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でうまく活用したい

このスクラップは2023/12/21にクローズされました