Maximum Callstack Exceeded with Quickcheck

Help
#1

I’m trying to test this library with quickcheck. My core data type is an recursive ADT representing an ICU Message Format string.

https://github.com/sharkbrainguy/opuntia/blob/master/src/FormatJS/IntlMessageFormat.purs#L237-L255

I’ve derived a Generic instance for MessageFormatElement, and defined an Arbitrary instance using genericArbitrary from purescript-quickcheck.

Running my tests immediately blows the stack, presumably because the genericArbitrary definition isn’t stacksafe?

I see that Gen has a MonadRec instance, can I use that or purescript-safely to call genericArbitrary in a stacksafe way?

Am I better off manually writing the recursive part of arbitrary?

Is there anything else clearly wrong about what I’m attempting?

Any help appreciated.

#2

genericArbitrary is probably unusable for recursive data structures. When writing a generator for a recursive structure you need to reduce the size at each level of the structure so that it will stop generating at some point. Also the generator itself needs to be sized to ensure that the size state is observed :wink:.

You could take a look at the generator for Json for an example of using size: https://github.com/purescript-contrib/purescript-argonaut-core/blob/master/src/Data/Argonaut/Gen.purs

1 Like
#3

Run into the same problem myself the other day. Substituting immediate recursive part with fix point solved it for me:

import Control.Lazy (fix)
import Data.NonEmpty ((:|))
import Test.QuickCheck.Arbitrary (class Arbitrary)
import Test.QuickCheck.Gen (oneOf)

data T a
  = Leaf a
  | V (T a)
  | B (T a) (T a)

instance arbT :: Arbitrary a => Arbitrary (T a) where
  arbitrary = fix $ \p -> oneOf (hd :| tl p)
    where
    hd   = Leaf <$> arbitrary
    tl p = [V <$> p, B <$> p <*> p]

YMMV.

2 Likes
#4

Thanks, that’s a great example to work from!

#5

Is this fix from the Control.Lazy package?

(also, TIL about :| and the Data.NonEmpty package)

#6

It is, the one and only :wink:

1 Like