bind 不容易缩小

Question

这是一个由来已久的难题。

h2. 问题

一个经典的例子是在包含有毒元素的情况下缩小一个 2D 矩阵


(def gen-matrix
  (gen/let [width gen/nat]
    (gen/vector (gen/vector gen/large-integer width))))

(quick-check 10000
              (prop/for-all [matrix gen-matrix]
               (->> matrix
                    (apply concat)
                    (not-any? #{42}))))
;; =>
{:result false,
 :seed 1466646880334,
 :failing-size 16,
 :num-tests 17,
 :fail [[[290 42 10 3 1 3 196]
         [-1793 3484 -5795 -206 -1 -8 464]
         [2 3 -1951 -761 -28829 5518 1]
         [-32 4477 1 -4086 0 1640 -22185]
         [-485 3156 -625 4082 -2 -845 513]
         [-3 -1 26 323 232 5 -1]
         [32 51 -1 240 -1814 0 -190]
         [2417 -4239 326 -4096 -8 1898 75]
         [-509 1 0 466 199 -1 10]
         [-23 5838 -441 30741 -6724 -1169 -171]
         [-4 3974 -1432 -4 698 -56 1210]
         [-2148 -6526 -1 453 19 -5343 461]]],
 :shrunk {:total-nodes-visited 31,
          :depth 8,
          :result false,
          ;; 更好地缩小到 [[[42]]]
          ;;
          ;; 注意这里的最小值可能具有相同的宽度（7），
          ;; 和最初的失败——唯一的原因是它能缩小宽度，
          ;; 只是因为它在生成一个全新矩阵时运气好，
          ;; 该矩阵宽度较小且恰好包含 42
          :smallest [[[0 42 0]]]}}


h2. 思想

- https://twitter.com/jacobstanley/status/745790758972624896
- https://twitter.com/DRMacIver/status/737390842462212096
- 尝试重用上次失败案例产生的值作为最佳方案
-- 如果我们记录了复合生成器每个子生成器生成的东西，并在缩小运行生成器时使用生成器相等性尝试重现那些值……它会很乱，但我认为这种混乱对用户来说是看不到的

Answer 1

参考资料：https://clojure.atlassian.net/browse/TCHECK-112（由gfredericks报告）