Haskell Quiz No.4

難易度: λ

今回は、与えられた値がリストのリストに含まれているかどうかを判定する問題です。

幅優先で探索する関数 bfs と深さ優先で探索する関数 dfs をそれぞれ定義してみましょう。

bfs :: Int -> [[Int]] -> Bool
bfs = undefined

dfs :: Int -> [[Int]] -> Bool
dfs = undefined

実行結果はだいたいこんな感じです。

$ stack repl -- Quiz4.hs
*Quiz4> xs = [[10..],[4,5,6],[7,8,9]]
*Quiz4> bfs 9 xs
True
*Quiz4> dfs 9 xs
.....

答えは次回

はじめに

前回の問題と答えは以下の通りです。

問題

難易度: λ

propIsDigit テストをパスするように Digit 型の Arbitrary インスタンスを定義してみましょう。

module Quiz3 where

import Test.QuickCheck
import Data.Char (isDigit)

newtype Digit = Digit Char
  deriving Show

propIsDigit :: Digit -> Bool
propIsDigit (Digit c) = isDigit c

instance Arbitrary Digit where
  arbitrary = undefined

テストは以下のように実行します。

$ stack repl --package QuickCheck -- Quiz3.hs
*Quiz3> quickCheck propIsDigit
+++ OK, passed 100 tests.

こたえ

実装方法はいくつかあるのですが、例えば elements を使う方法だとこんな感じです。

instance Arbitrary Digit where
  arbitrary = Digit <$> elements "1234567890"

ちょっと反則っぽいですが suchThat を使う方法もありそうですね。

instance Arbitrary Digit where
  arbitrary = Digit <$> arbitrary `suchThat` isDigit

こんな方法もあるよーと言う方は教えてください!

Haskell Quiz No.3 の解説

QuickCheck を使っている人にとっては簡単な問題だったと思います。

逆に全く使ったこと無い人にとっては、結構難しかったのではないでしょうか。

Arbitrary 型クラス

Arbitrary 型クラスは QuickCheck パッケージの Test.QuickCheck.Arbitrary で定義されています。

Minimal complete definitionarbitrary メソッド (関数) です。

Minimal complete definition とは、型クラスのインスタンスを全て実装しなくても Minimal complete definition だけ実装すれば全てのメソッドが (デフォルト実装で) 利用できるというものです。効率が悪い場合もあるので、その場合は自分で定義を上書きします。

つまり、今回の場合だと arbitrary メソッドさえ定義してしまえば shrink メソッドも同様に利用可能になるということです。

実際の定義は以下の通りです。

class Arbitrary a where
  arbitrary :: Gen a

  shrink :: a -> [a]
  shrink _ = []

arbitrary メソッド

arbitrary の型は Arbitrary a => Gen a なので、最初はどうやって定義して良いのか困惑してしまうかもしれません。

Gen a はランダムな値を生成するジェネレータを意味する型です。

定義の方法は本当に色々ありますが、まずは基本のユーティリティ関数を抑えておきましょう。

Generator combinators に列挙されている関数の一部をご紹介します。

elements

与えられたリストの値を元に Gen a を作ります。

*Quiz3> :t elements
elements :: [a] -> Gen a

*Quiz3> sample' $ elements "1234567890"
"55316502254"

今回の問題もこれを使って isDigit に通る値のみをリストに含めてあげたら良いのです。

choose

タプルで指定した範囲で値を生成します。その際 Random 型クラスのクラス制約が発生することに注意してください。

*Quiz3> :t choose
choose :: random-1.1:System.Random.Random a => (a, a) -> Gen a

*Quiz3> sample' $ choose (1,10)
[3,7,5,9,4,4,6,2,6,6,1]

oneof

oneof[Gen a] からランダムに1つ Gen a を選びます。

*Quiz3> :t oneof
oneof :: [Gen a] -> Gen a

*Quiz3> sample' $ oneof [choose (1,3)]
[3,2,3,3,3,2,3,1,2,1,1]

*Quiz3> sample' $ oneof [choose (1,3), choose (10,30)]
[18,26,2,17,1,1,25,13,25,16,2]

frequency

oneof と似ていますが、完全にランダムではなく頻出度合いを制御することができます。

*Quiz3> :t frequency
frequency :: [(Int, Gen a)] -> Gen a

*Quiz3> sample' $ frequency  [(1,choose (1,1)), (100,choose (100,100))]
[100,100,100,100,100,100,100,100,100,100,100]

*Quiz3> sample' $ frequency  [(30,choose (1,1)), (70,choose (100,100))]
[100,1,1,100,100,1,100,100,100,100,1]

suchThat

第二引数の述語を満たす値だけで Gen a を作ります。

*Quiz3> :t suchThat
suchThat :: Gen a -> (a -> Bool) -> Gen a

*Quiz3> sample' $ suchThat arbitrary even
[0,0,2,6,-8,10,-10,-6,-6,-6,-22]

*Quiz3> sample' $ suchThat arbitrary odd
[-1,1,3,5,-5,1,11,-9,7,-11,-13]

vectorOf

与えられた長さの [Gen a] を作ります。

*Quiz3> :t vectorOf
vectorOf :: Int -> Gen a -> Gen [a]

*Quiz3> sample' $ vectorOf 2 (arbitrary :: Gen Int)
[[0,0],[0,-2],[0,4],[-3,-2],[2,-5],[6,-8],[1,-10],[-12,9],[3,-5],[13,4],[-8,12]]

shrink メソッド

参考: What is a shrink, with regard to Haskell’s QuickCheck?

shrink はテストに失敗した際にできるだけ小さな反例を返すために利用されるようです。

verboseCheck 関数を使えば、実際に生成されたテストケースと結果を全てみることができます。

例として 5 を含まないリストという prop でチェックしてみましょう。(結果は少し見やすいように整形してあります)

>>> prop l = all (/= 5) l
>>> verboseCheck prop
Passed:[]
Passed:[]
Passed:[1,2]
Passed:[2,2]
Passed:[-1,1,2]
Passed:[3,-1]
Passed:[-4,-4,-5,3,-4]
Passed:[-6,1,4,-6,-5]
Passed:[4]
Passed:[2,-2]
Passed:[2,8,7]
Passed:[-7,-8,7,6,9,-10,1]
Passed:[-10,11,2]
Passed:[12,0,3,-12,7,-13,-6,9,-8,7,-10,9]
Passed:[4,4,-11,3,-7]
Passed:[2,1,-9]
Passed:[16,3,-8,14,-7,-7,9,-3,-15,3,-10,-14,9,-8,-3]
Passed:[-2,0,-6,0,4,8,17,13]
Passed:[1,15,17]
Passed:[9,-17,-15,-16,-18,16,-19,15]
Passed:[0,10,6,8,0,4,-9,-12,20,0,3,1,-2,14,13,-11]
Passed:[16,-5,-21,2,2,-6,6]
Passed:[-22,14,10,-18,-22,-10,8,8,-14,12,-22]
Passed:[-18,18,0,-1,-16,-4,13,0,11,-20,10,11,0,-9]
Passed:[-9,22,-2,-18,-9,-4,21,-7,0,9,-11]
Passed:[9,21,11,-17,8,-10,0,6,16,17,6,-16,10,24,-7,9,-1,11,-14,-22,-1,-5,2,11,12]
Passed:[-9,-21,25,-11,9,-11,-14,16,-9,-17,-8,9,4,-10,-6,-6,-17,-21,-26,-12]
Passed:[-8,-11,-21,3,4,13,27,-24,-13,-12,-21,-13,-25,10]

Failed:[25,10,-17,27,8,17,5,14,-1,22,-13,13,-9,-23,26,16,0,10]

生成されるリストがどんどん大きくなり、やっとリストに 5 を含む反例 [25,10,-17,27,8,17,5,14,-1,22,-13,13,-9,-23,26,16,0,10] を見つけました。この反例をそのまま返しても良いのですが、もしかしたらもっと小さな反例が見つかるかもしれません。

verboseCheck は実際にさきほどの反例を、今度は逆に減らしてテストしていきます。

*** Failed!
Passed:[]
Passed:[22,-13,13,-9,-23,26,16,0,10]
Failed:[25,10,-17,27,8,17,5,14,-1]   -- より小さい反例が見つかった
Passed:[]
Failed:[8,17,5,14,-1]                -- より小さい反例が見つかった
Passed:[]
Failed:[5,14,-1]                     -- より小さい反例が見つかった
Passed:[]
Passed:[14,-1]
Failed:[5,-1]                        -- より小さい反例が見つかった
Passed:[]
Passed:[-1]
Failed:[5]                           -- 最小の反例が見つかった
Passed:[]
Passed:[0]
Passed:[3]
Passed:[4]

Falsifiable (after 29 tests and 5 shrinks):
[5]

ということで Falsifiable (after 29 tests and 5 shrinks): [5]テストの29回目に反例が見つかりました。さらにその反例を5回小さくしたよ という意味になります。

デフォルト実装では shrink _ = [] となっていたので、見つかった反例をそのまま返すようですね。(haddock を見るともっと詳しく書いてあるので、気になる方はそちらをご参照ください)

quickcheck-instances パッケージ

ここまでで QuickCheck がどんなものか何となくわかってもらえたと思います。

base パッケージで提供されている型については、ほとんどデフォルトで Arbitrary のインスタンス定義があります。

しかしながら、time パッケージの UTCTime 型や text パッケージの Text 型などのインスタンス定義は別途自分で書かなくてはなりません。

quickcheck-instances パッケージはそういった、よく使うパッケージのインスタンス定義をまとめたものです。

このパッケージの定義で満足いかない場合は自分でカスタマイズするというようにすれば、効率的に開発が進むと思いますよ!

Haskell の入門書を読み終えたあとは・・・?

Haskell の入門書を読み終わった後のオススメの勉強法は以下の2つです。

  • アカデミックコース: 論文を読む
  • エンジニアコース: ライブラリとアプリケーションのソースコードを読む

論文の知識が無いと読めないライブラリもありますし、実装力がないと深い理解が得られない論文もあると思いますが、続けていると不思議とわかるようになります。

また、驚くべきことに Haskell 界隈ではカジュアルにドキュメントのリンクが論文だったりしますが、時間が経てばわかりやすい解説がいくつも出てくるものなので、その時はわからなくてもそのうちわかるようになるかもしれません。

ちなみに QuickCheck に関連する論文も (いくつか) ありますよ。

まとめ

shrink なんて使ったことなかったので、今まで良くわかんない関数でしたが、今後機会があれば定義してみようと思います。

QuickCheck はランダムテストだと思えば、すぐに理解できますよ!性質テストって言われると難しい感じがしてしまいます・・・。(僕だけかも)

以上です。