The applicative List instance runs forever in the QuickCheck / Checkers compliance law test

Question

I want to implement a regular applicative instance for lists using my user-defined list:

import Control.Monad import Test.QuickCheck import Test.QuickCheck.Checkers import Test.QuickCheck.Classes data List a = Nil | Cons a (List a) deriving (Eq, Ord, Show) instance Functor List where fmap f (Cons x xs) = Cons (fx) (fmap f xs) fmap f Nil = Nil instance Applicative List where pure x = Cons x Nil (<*>) Nil _ = Nil (<*>) _ Nil = Nil (<*>) (Cons f fs) xs = (+++) (fmap f xs) (fs <*> xs) (+++) :: List a -> List a -> List a (+++) (Cons x Nil) ys = Cons x ys (+++) (Cons x xs) ys = Cons x xs' where xs' = (+++) xs ys instance Arbitrary a => Arbitrary (List a) where arbitrary = sized go where go 0 = pure Nil go n = do xs <- go (n - 1) x <- arbitrary return (Cons x xs) instance (Eq a) => EqProp (List a) where (=-=) = eq main = do let trigger = undefined :: List (Int, String, Int) quickBatch $ applicative trigger 

My code passes all application tests to checkers, except for one, the law of composition. When testing the law of composition, an error does not occur, it just does not end.

Does my code persist forever in some way, I can’t see, or is it just a slow process of validating the composer?

This is the error message that I get if I run -c at runtime Checkers:

 applicative: identity: +++ OK, passed 500 tests. composition: *** Failed! Exception: 'user interrupt' (after 66 tests): Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> Nil)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> Nil)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) Cons (-61) (Cons (-24) (Cons 56 (Cons (-10) (Cons 28 (Cons 5 (Cons (-5) (Cons 33 (Cons 18 (Cons 47 (Cons 43 (Cons 43 (Cons (-58) (Cons 35 (Cons (-52) (Cons (-52) (Cons (-41) (Cons 3 (Cons (-7) (Cons (-53) (Cons (-22) (Cons (-20) (Cons (-12) (Cons 46 (Cons (-53) (Cons 35 (Cons (-31) (Cons (-10) (Cons 43 (Cons (-16) (Cons 47 (Cons 53 (Cons 22 (Cons 8 (Cons 1 (Cons (-64) (Cons (-39) (Cons (-57) (Cons 34 (Cons (-31) (Cons 20 (Cons (-39) (Cons (-47) (Cons (-59) (Cons 15 (Cons (-42) (Cons (-31) (Cons 4 (Cons (-62) (Cons (-14) (Cons (-24) (Cons 47 (Cons 42 (Cons 61 (Cons 29 (Cons (-25) (Cons 30 (Cons (-20) (Cons 16 (Cons (-30) (Cons (-38) (Cons (-7) (Cons 16 (Cons 19 (Cons 20 Nil)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) homomorphism: +++ OK, passed 500 tests. interchange: +++ OK, passed 500 tests. functor: +++ OK, passed 500 tests. 

If one of the functions is slow, I think it is (+++) , but I do not know how the GHC executes the code well enough to understand why.

Update:

Law of composition:

 pure (.) <*> u <*> v <*> w = u <*> (v <*> w) 

What can I show with my code for simple examples:

 Cons (+1) Nil <*> (Cons (*2) Nil <*> Cons 1 (Cons 2 (Cons 3 Nil))) 

and

 pure (.) <*> Cons (+1) Nil <*> Cons (*2) Nil <*> Cons 1 (Cons 2 (Cons 3 Nil)) 

Both give the same result, therefore, why the law of composition never ends, I am very puzzled. Perhaps this is a problem with the checkers library?

Answer 1

My first thought was that go received a negative argument and a loop. However, when you change it to use trace and throw an error if n < 0 , I find this to be much simpler: your code is just very slow.

Here, part I, modified ( go' , was used for tracing, but I shorted it for benchmarking):

 import Debug.Trace (+++) :: List a -> List a -> List a {-# INLINE (+++) #-} (+++) (Cons x Nil) ys = Cons x ys (+++) (Cons x xs) ys = Cons x xs' where xs' = (+++) xs ys maxListSize = 10 instance Arbitrary a => Arbitrary (List a) where arbitrary = sized go'' where go'' n = go' $ mod n maxListSize go' n = if n < 0 then error ("bad n:" ++ show n) else trace (show n ++ " , ") $ go n go 0 = pure Nil go n = do xs <- go' (n - 1) x <- arbitrary return (Cons x xs) 

Checking the trace for some infinite loop, I found that things never stopped, n continued to decrease, and then went back for the next test. It just took a few seconds for one test when it slowed down. Remember that you are trying to run 500 tests.

My tests are not strict, but here is what I got ( x is a module in the range [1..18] ):

A short regression was 5.72238 - 2.8458 x + 0.365263 x^2 . When I ran the track, n continued to grow. Although I'm not sure how the testing is done, if it increases n every test, then n will go up to 500 .

The formula is not really fair, but let it be considered decent. (I think it should be, since the algorithm is O(n^2) .)

Then running all the tests will take about 25 hours on my machine.

PS Since all tests pass at reasonable boundaries on n , and I can’t find the error, I think your code is correct.