Haskell Quiz No.4

難易度: λ

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

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

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

答えは次回

はじめに

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

問題

難易度: λ

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

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

こたえ

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

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

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

Haskell Quiz No.3 の解説

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

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

Arbitrary 型クラス

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

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

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

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

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

arbitrary メソッド

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

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

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

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

elements

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

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

choose

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

oneof

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

frequency

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

suchThat

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

vectorOf

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

shrink メソッド

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

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

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

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

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

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

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

以上です。