Generating well-typed terms that are not "useless" [pdf]

The use of quotes around "Useless" becomes clear in

> decoupling the generation of types and expressions significantly biases generation towards functions that do not use their arguments.

> Such “use-less” function arguments lead to wasted computation, both in terms of generation time (as the code that generates such arguments is essentially dead) and in terms of compilation time (as the test runner now needs to compile a larger program).

Using laziness to avoid generating parts of an expression until it's needed is a really nice idea. The LazySmallCheck package[1] took this approach, but was limited in the types of data it could produce (e.g. it couldn't generate functions). This was extended by LazySmallCheck2012[2], but that seems to be unmaintained and doesn't work with more recent GHC versions.

(Note that these are named in reference to SmallCheck[3], which takes the approach of enumerating concrete values in order of "size"; as an alternative to the more widely-used QuickCheck[4], which generates concrete values at random, and tries to "shrink" those which trigger a failure)

[1] https://hackage.haskell.org/package/lazysmallcheck

[2] https://github.com/UoYCS-plasma/LazySmallCheck2012

[3] https://hackage.haskell.org/package/smallcheck

[4] https://hackage.haskell.org/package/QuickCheck

Looks like a very interesting paper for everyone trying to test any kind of tool that works on a (functional) language.

Love the Acknowledgement section.