QuickCheck で特定の文字からなるランダムな文字列の生成
DFA/NFA のテストとして、特定の文字からなるランダムな文字列をテストデータとしたい。例えば、アルファベットが文字 a と b のみからなるDFAに対しては、"a", "ab", "aaaababa" などの文字列を生成したい。
しばらく方法が分からず悩んでいたが以下のように listOf(または listOf1) と elements のくみあわせでできた。
rndString0 str = listOf1 (elements str) *FA> :t listOf1 listOf1 :: Gen a -> Gen [a] *FA> :t elements elements :: [a] -> Gen a *FA> :t rndString0 rndString0 :: [a] -> Gen [a]
以下のように使う。listOf だと空文字列も含まれるが、listOf1 だと１文字以上の文字列になるので、目的によって使い分ける。
*FA> sample (rndString0 "ab") "b" "bb" "ab" "baaa" "bbbabb" "bbabaaba" "aaabba" "aaaabababb" "abaaabbbaaabab" "ababbaaabaabbabb" "baa" *FA> sample (rndString0 [0,1,2,3,4,5]) [4] [3] [3,4,0,4] [5,4,1,3,1] [2,3] [4,0,0,4,1,1,0,1,1] [5,2,5,1,0,5,3] [4,5,3,2,2,0,1,2,4,5] [4,1,1,3,5] [3,3,2,4,3,5,3,1,5,5,4,3,2] [1,2,5,4,1,4,2,1,4,4,0,4,0,4,3,0,2,4]
randString0 をDFAのアルファベット用に修正して、DFA の（幾つかの）テストができる。例えば、DFAと等価な状態数最小のDFAは、任意の文字列について受理するかしないか、が等しくなければならない。具体的なオートマトン(ここでは正規表現 "a(a|b)*ab" と等価な dfa_aabab )を用いて以下のようなテストを走らせることができる。
prop_minDFA dfa = forAll (rndString dfa) (\str -> accept dfa str == accept (minimizeDFA dfa) str) *FA> quickCheck (prop_minDFA dfa_aabab) +++ OK, passed 100 tests. *FA>
いい感じ。
さらに、既存の、正しいことが分かっているHaskell の正規表現と比較してみよう。Text.Regex.Posix をインポートして、以下のように書けた。
regexpMatch reg str = str R.=~ reg :: Bool prop_DFAREG dfa reg = forAll (rndString dfa) (\str -> accept dfa str == regexpMatch reg str) *FA> quickCheck (prop_DFAREG dfa_aabab "^a(a|b)*ab$") +++ OK, passed 100 tests.
ここで、比較する正規表現は "a(a|b)*ab" では部分一致を許してしまうため、テストをパスしない。"^a(a|b)*ab$" としなくてはならない。
