该示例显示了集成收缩的局限性 [英] Example that shows the limitations of integrated shrinking

问题描述

我刚刚观看了视频，该视频呈现了集成收缩的概念用于基于属性的测试.与类型定向收缩相比，该方法似乎具有一些优势，但是在

I just watched a video that presents the notion of integrated shrinking for property based tests. The approach seems to have some advantages over type directed shrinking, however it was pointed out in this reddit thread that the integrated shrinking approach does not fit well in the case of monadic generators:

以这种方式收缩并不适合发电机的单调风格.这是一个示例，请考虑生成一个任意列表(暂时忽略终止):

Doing shrinking in your way does not fit well with a monadic style for generators. Here is an example, consider generating an arbitrary list (ignore termination for now):

do x <- arbitrary
   xs <- arbitrary
   return (x:xs)

现在，收缩的默认行为是先收缩x(使xs保持恒定)，然后收缩xs(使xs保持恒定)，这严重限制了收缩(局部最小值的概念现在不那么牢固了).

Now, the default behavior of your shrinking would first shrink x (holding xs constant), and then shrink xs (holding x constant), which severely limits the shrinking (the concept of local minimum is now a lot less strong).

我将以上评论视为综合收缩可能无法提供全局最小反例".但是，由于 hedgehog 似乎为了能够找到列表中失败的属性的最小计数器示例，我想知道是否有一个示例可以显示上面引用中指出的缺点.

I read the above comment as "integrated shrinking might fail to provide a global minimum counter example". However, since hedgehog seems to be able to find minimal counter examples for failed properties on lists, I was wondering if there is an example that could show the drawback pointed out in the quote above.

推荐答案

在微积分方面，问题在于您没有遵循负梯度(最陡下降)，而是先沿1轴最小化，然后最小化沿着另一个轴.根据这种类比，很容易提出至少一个人为的例子-考虑函数

In calculus terms, the problem is that you aren't following the negative gradient (steepest descent), instead you're minimizing along 1 axis first and then minimizing along the other axis. Based on this analogy, it is easy to come up with at least a contrived example - consider the function

-- f x y = ((x^2 - 1)^2 - 0.2*x) * ((y^2 - 1/2)^2 - 0.1*y)
f x y = (x^4 - 2.2*x^2 + 1) * (y^4 - 1.1*y^2 + 1/4)

，我们正在针对属性 f x y>对其进行测试.0 ，假设有一个最小示例，其点最接近原点(0，0).根据首先开始收缩的位置，完全有可能最终接近(±1，0)，因为先调整 x 然后不允许 y 进行很大的更改.但是，在理想情况下，您可能希望以接近(0，±1/2)的某个地方结束，以满足最小值标准.

and we're testing it for the property f x y > 0, and let's say a minimal example would have a point closest to the origin (0, 0). Depending on where you first start shrinking, it is entirely possible that you end up close to (±1, 0) because you adjust x first and then don't allow y to change much. However, in an ideal situation, you'd want to end up somewhere close to (0, ±1/2) to satisfy the minimality criterion.

这篇关于该示例显示了集成收缩的局限性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！