<div dir="ltr">alternatively, would it be possible to have a default definition of shrink using generics? (I'm still chewing on your email, but sounds like the current definition doesn't have a default generic method!)</div>

<div class="gmail_extra"><br><br><div class="gmail_quote">On Thu, Nov 21, 2013 at 7:27 PM, Reid Draper <span dir="ltr"><<a href="mailto:reiddraper@gmail.com" target="_blank">reiddraper@gmail.com</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I originally sent this message to the QuickCheck mailing list,<br>
but haven't heard anything in a while, and realized there are<br>
only ten subscribers. Below is the original message, any feedback<br>
appreciated.<br>
<br>
---<br>
<br>
I have an idea to eliminate the `shrink` function from the `Arbitrary` type<br>
class. Currently, users can optionally implement shrinking manually, this tends<br>
to be boilerplate code and is "...clearly a generic programming problem" [1].<br>
Further, users often have to create separate types to accommodate their<br>
domain's restrictions. For example, a user may wish to only generate<br>
power-of-two numbers for their test. Their code simply uses `Int`, but with<br>
QuickCheck they must create a `newtype` wrapper and implement this logic in<br>
both the `arbitrary` and `shrink` implementation. My idea is to<br>
eliminate the `shrink` function, and to integrate shrinking with the<br>
`arbitrary` function. Currently, the type for `arbitrary` is:<br>
<br>
<br>
    arbitrary :: Gen a<br>
<br>
<br>
and `Gen` has the definition:<br>
<br>
<br>
    newtype Gen a = MkGen{ unGen :: StdGen -> Int -> a }<br>
<br>
<br>
I suggest that instead of the inner-function returning `a`s, it should return<br>
`RoseTree a`. The root of the tree is the generated value, and the rest of the<br>
tree is all of the ways to shrink the value. Here's how things would fit<br>
together:<br>
<br>
<br>
    data RoseTree a = RoseTree a [RoseTree a]<br>
<br>
    -- this is the same as the current Gen<br>
    newtype Generator a = Gen { unGen :: StdGen -> Int -> a }<br>
<br>
    newtype Gen a = MkGen { unGen :: Gen (RoseTree a) }<br>
<br>
<br>
Conveniently, `Gen` still has a unary type constructor of `a`. Further, if<br>
users have implemented their `arbitrary` implementations in terms of the<br>
QuickCheck combinators, their code won't have to change at all (I don't think…).<br>
The lower-level combinators would be updated to manipulate trees, with<br>
functions like `joinRose` and `filterRose`. Let's next look at how `Gen`<br>
would implement the monad type class:<br>
<br>
<br>
    instance Monad Gen where<br>
        return = MkGen . return . return<br>
<br>
        gen >>= f = MkGen $ helper (unGen gen) (unGen . f)<br>
            -- sequence is from Data.Traversable<br>
            where helper m k = m >>= \y -> fmap joinRose $ sequence $ fmap k y<br>
<br>
<br>
The implementation of `return` is clear. `>>=` isn't too bad either: the<br>
function provided to bind will return `Gen b`'s, and `joinRose` and `sequence`<br>
help us pull this `Generator (RoseTree b))` 'out', much like `join` does. This<br>
means our users can still write code like:<br>
<br>
<br>
    (arbitrary :: Gen [Int]) >>= elements<br>
<br>
<br>
Which brings up a good point. The above code has an issue, `elements` is a<br>
partial function with respect to the empty list. With the current<br>
implementation, we'd use the `NonEmptyList` modifier, which much respect this<br>
predicate both during generation and shrinking. This change would allow all<br>
predicates to be expressed simply with `suchThat`, which, since it acts on both<br>
values _and_ shrink trees, applies the predicate in both places. The<br>
implementation of `suchThat` would have to unwrap `Gen`, and apply `roseFilter`<br>
to the `RoseTree` inside of `Generator`, using `fmap`.<br>
<br>
I have implemented the above description in my Clojure port of QuickCheck,<br>
called simple-check [1], and it seems to be working quite nicely. Further, I<br>
suspect Erlang QuickCheck [3] is doing something similar, though their<br>
implementation is not open source, I can't presume too much.<br>
<br>
Clearly this would be a big change, and my goal now is simply to start a<br>
discussion: how does this sound? What's wrong, what's likely to break? Feedback<br>
and criticism welcome.<br>
<br>
Reid<br>
<br>
<br>
[1] Scrap your boilerplate with class: extensible generic functions: <a href="http://research.microsoft.com/pubs/67439/gmap3.pdf" target="_blank">http://research.microsoft.com/pubs/67439/gmap3.pdf</a><br>
<br>
[2] <a href="https://github.com/reiddraper/simple-check" target="_blank">https://github.com/reiddraper/simple-check</a><br>
<br>
[3] <a href="http://www.quviq.com/index.html" target="_blank">http://www.quviq.com/index.html</a><br>
<br>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org">Libraries@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/libraries" target="_blank">http://www.haskell.org/mailman/listinfo/libraries</a><br>
</blockquote></div><br></div>