0
votes

I'm working through the wonderful Haskell Book. While solving some exercises I ran QuickCheck test that took a relatively long time to run and I can't figure out why.

The exercise I am solving is in Chapter 16 - I need to write a Functor instance for

data Parappa f g a = 
  DaWrappa (f a) (g a)

Here is a link to the full code of my solution. The part I think is relevant is this:

functorCompose' :: (Eq (f c), Functor f) 
                => Fun a b -> Fun b c -> f a -> Bool
functorCompose' fab gbc x =
  (fmap g (fmap f x)) == (fmap (g . f) x)
  where f = applyFun fab
        g = applyFun gbc

type ParappaComp = 
     Fun Integer String 
  -> Fun String [Bool] 
  -> Parappa [] Maybe Integer
  -- -> Parappa (Either Char) Maybe Integer
  -> Bool


main :: IO ()
main = do
  quickCheck (functorCompose' :: ParappaComp) 

When I run this in the REPL it takes ~6 seconds to complete. If I change ParappaComp to use Either Char instead of [] (see comment in code), it finishes instantaneously like I'm used to seeing in all other exercises.

I suspect that maybe QuickCheck is using very long lists causing the test to take a long time, but I am not familiar enough with the environment to debug this or to test this hypothesis.

  1. Why does this take so long?
  2. How should I go about debugging this?
1
[] is a list. An arbitrary list can have an arbitrary number of elements, so that means it can take some time to perform a mapping over the entire list. For an Either, this is a single element. - Willem Van Onsem
It also looks like arbitrary Funs that accept lists, including Strings, are very slow. Switch your intermediate type from String to Char, and it completes quickly. - K. A. Buhr
@K.A.Buhr, I tried that out and you're right! Can you elaborate on how you found out? - javinor
No special insight -- I just fiddled around with your example for bit and discovered that String was the problem. I then tested Funs with list arguments in isolation and saw that they performed quite poorly. - K. A. Buhr

1 Answers

3
votes

I suspect that maybe QuickCheck is using very long lists causing the test to take a long time, but I am not familiar enough with the environment to debug this or to test this hypothesis.

I'm not sure of the actual cause either, but one way to start debugging this is to use the collect function from QuickCheck to collect statistics about test cases. To start, you can collect the size of the result.

  • A simple way to obtain a size is by using the length function, requiring the functor f to be Foldable
  • You will need to implement or derive Foldable for Parappa (add {-# LANGUAGE DeriveFoldable #-} at the top of the file, add deriving Foldable to Parappa)
  • To use collect, you need to generalize Bool to Property (in the signature of functorCompose' and in the type synonym ParappaComp)
functorCompose' :: (Eq (f c), Functor f, Foldable f) 
               => Fun a b -> Fun b c -> f a -> Property
functorCompose' fab gbc x =
  collect (length x) $
    (fmap g (fmap f x)) == (fmap (g . f) x)
  where f = applyFun fab
        g = applyFun gbc

With that you can see that the distribution of the lengths of generated lists is clustered around 20, with a long tail up to 100. That alone doesn't seem to explain the slowness, as one would expect that traversing lists of that size should be virtually instantaneous.