[Haskell-cafe] Hedgehog - Integrated shrinking, shrinks obey invariants by construction.

Li-yao Xia lysxia at gmail.com
Fri Jun 15 12:50:04 UTC 2018

On 06/15/2018 07:31 AM, Petr Pudlák wrote:
> That's interesting! Could you please elaborate how this is implemented?

Sure. Whereas QuickCheck declares "shrink" as a function, in Hedgehog 
generating and shrinking are performed simultaneously. Instead of 
generating a single value, we can generate a rose tree of them, where 
the main output is at the root, and the other nodes carry shrunk 
versions of it, with the smallest ones at the leaves. It works quite 
nicely and efficiently in Haskell thanks to laziness, so that the 
shrinking part only happens as needed.

The main drawback might be that there is some duplicated work during 
shrinking ((>>=) applies its second argument to different arguments), 
but it is quite minor since shrinking is only needed in exceptional 
cases, and it usually terminates in few steps.


More information about the Haskell-Cafe mailing list