अनुप्रयोगी उदाहरण QuickCheck साथ रचना कानून की परीक्षा में हमेशा के लिए चलाता है/चेकर्स

Question

मैं सूचियों के लिए नियमित रूप से अनुप्रयोगी उदाहरण लागू करने के लिए, मेरे customly निर्धारित सूची का उपयोग कर चाहते हैं:

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 (f x) (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 

मेरे कोड चेकर्स में सभी अनुप्रयोगी परीक्षण गुजरता एक को छोड़कर, रचना कानून। रचना कानून का परीक्षण करते समय कोई त्रुटि नहीं होती है, यह कभी खत्म नहीं होती है।

क्या मेरा कोड किसी भी तरह से अनन्त रूप से दोबारा शुरू होता है, मैं देखने में असमर्थ हूं, या यह कंपोजिटन कानून का परीक्षण करने के लिए बस धीमा है? अगर मैं चेकर्स निष्पादन के दौरान Control-C

यह मैं त्रुटि संदेश है:

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. 

हैं कार्यों में से एक धीमी है, मुझे लगता है कि यह (+++) है, लेकिन मैं पता नहीं कैसे GHC क्यों समझने के लिए पर्याप्त कोड निष्पादित करता है।

अद्यतन:

रचना कानून है:

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

कौन सा मैं सरल उदाहरण के लिए मेरे कोड के साथ काम करता है दिखा सकते हैं:

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

और

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

दोनों वही देना नतीजतन, तो संरचना कानून कभी खत्म क्यों नहीं हुआ है मुझे स्टंप किया गया है। क्या यह checkers लाइब्रेरी के साथ समस्या हो सकती है?

Answer 1

मेरा पहला विचार था कि go को नकारात्मक तर्क और लूपिंग मिल रही थी। हालांकि, trace का उपयोग करने के लिए इसे संशोधित करते समय और n < 0 पर कोई त्रुटि डालें, मैंने पाया कि यह बहुत आसान है: आपका कोड वास्तव में धीमा है।

यहाँ भाग मैं संशोधित है (go' अनुरेखण के लिए इस्तेमाल किया गया था, लेकिन मैं कम बेंच मार्किंग के लिए यह सर्किट):

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) 

अनंत लूप के कुछ प्रकार के लिए ट्रेस जाँच हो रही है, मैंने पाया कि चीजें प्रगति बंद कर दिया कभी नहीं, n अगले परीक्षण के लिए बैक अप लेने के बाद घटते रहे। यह धीमा होने पर एक परीक्षण के लिए सेकंड लिया गया। याद रखें कि आप प्रत्येक परीक्षा में 500 चलाने की कोशिश कर रहे हैं।

मेरे मानक कठोर नहीं हैं, लेकिन यहाँ (x, मापांक है रेंज [1..18] में) मैं क्या मिल गया है:

त्वरित प्रतिगमन पाया 5.72238 - 2.8458 x + 0.365263 x^2। जब मैंने ट्रेस चलाया, n बढ़ता रहा। हालांकि मुझे यकीन नहीं है कि परीक्षण कैसे चल रहे हैं, अगर यह n प्रत्येक परीक्षण को बढ़ाता है, तो n500 तक पहुंच जाएगा।

सूत्र वास्तव में उचित नहीं है, लेकिन मान लीजिए कि यह एक सभ्य बाध्य है। (मुझे लगता है कि यह होना चाहिए क्योंकि एल्गोरिदम O(n^2) है।)

तो सभी परीक्षणों मोटे तौर पर 25 घंटे का समय लग जाएगा, मेरे मशीन पर चल रहा।

पीएस चूंकि सभी परीक्षण n पर उचित सीमाओं के लिए पास होते हैं और मुझे कोई बग नहीं मिल रहा है, मुझे लगता है कि आपका कोड सही है।