QuickCheck系統のGenのfilter(suchThat)実装比較

Gen#filter · Issue #5 · xuwei-k/scalaprops · GitHub

こういうissueを投げたあとで、オープンではない場所で色々話していた際にちょっと調べてみたのでメモ。

filter(suchThat)の挙動

あるジェネレータから条件を見たす値のみを出力したい場合に使う

-- こんなシグネチャ
Gen a -> (a -> Bool) -> Gen a

処理的には

  1. 値をランダムに生成して
  2. 生成した値が述語を満たすかチェックし
  3. 満たすならその値をGenで包んで返す
  4. そうでない場合はseedを変えてやり直し

問題点

  • 条件を満たさなければ再生性を行わなければならない都合上、再帰関数にするかwhileでぶん回す必要がある
  • 実装次第で無限ループに陥る
  • 無限ループしない場合でも処理の遅延につながる

対策

  • 生成回数の上限を決める
  • 生成失敗を組み込む
  • 別の機能で置き換える
  • 覚悟を決めてぶん回す

lazyかどうかは関係ないはず。

上限を決める

https://github.com/clojure/test.check/blob/7ed9f927047366d14f160a3a23fde5e6bab629f2/src/main/clojure/clojure/test/check/generators.clj#L299

思い処理でなければ現実的な時間に収まる。 ただし、生成方法によってはかならずExhaustedになる。 また、テストがエラーとして扱われる。

生成失敗を組み込む

https://github.com/rickynils/scalacheck/blob/333307dc1b7dd022641191c5085222583cfc3994/src/main/scala/org/scalacheck/Gen.scala#L33

ただし、この方針を採用すると他の機能にかなりの影響を与える。

  • Genの生成結果を取得して新たなGenを作る際に失敗処理を組み込む必要がある
  • とくにCoArbitraryとの相性が悪い

別機能で置き換える

https://github.com/BurntSushi/quickcheck/blob/d282c811a4c419ae4cd997b1093636d88d5c573a/examples/reverse_single.rs#L15

定型処理になるしテスト失敗になる確率が増えるが、安定はする。

気合いでぶん回す

https://github.com/fsharp/FsCheck/blob/91ebaf7b7c2453212e80b9d193f343e26975c356/src/FsCheck/Gen.fs#L317

  • タイムアウト機能必須(なかったら無限ループに陥る)
  • 条件を満たす値をみつけるまで繰り返すため遅い
  • ユーザは気楽にフィルタリングできる

まとめ

妥協できるかどうかはユーザ次第。

以下追記