सहयोगीता, कम्यूटेटिविटी इत्यादि के लिए स्वचालित रूप से और दृढ़ता से एक फ़ंक्शन का परीक्षण

Question

क्या उच्च आदेश फ़ंक्शन isAssociative बनाना संभव है जो दो तर्कों का एक और कार्य करता है और यह निर्धारित करता है कि वह कार्य सहयोगी है या नहीं?

इसी प्रकार के प्रश्न लेकिन इस तरह के commutativity के रूप में अन्य संपत्तियों के लिए भी।

यदि यह असंभव है, वहाँ किसी भी भाषा में यह स्वचालित के किसी भी तरीका है? अगर एग्डा, कोक या प्रोलॉग समाधान है तो मुझे रूचि है।

मैं एक जानवर बल समाधान है कि बहस के हर संभव संयोजन की जाँच करता है और कभी नहीं समाप्त हो जाता है की कल्पना कर सकते हैं। लेकिन इस संदर्भ में "कभी समाप्त नहीं होता" एक अवांछनीय संपत्ति है।

Answer 1

मुझे लगता है कि हास्केल ऐसी चीजों के लिए बहुत उपयुक्त नहीं है। आमतौर पर आप जांच के लिए पूरी तरह से विपरीत करते हैं। आप घोषणा करते हैं कि आपके ऑब्जेक्ट में कुछ गुण हैं और इस प्रकार कुछ विशेष तरीके से उपयोग किया जा सकता है (Data.Foldable देखें)। कभी कभी आप अपने सिस्टम को बढ़ावा देना चाहते हो सकता है:

import Control.Parallel 
import Data.Monoid 

pmconcat :: Monoid a => [a] -> a 
pmconcat [x] = x 
pmconcat xs = pmconcat (pairs xs) where 
    pairs [] = [] 
    pairs [x] = [x] 
    pairs (x0 : x1 : xs') = y `par` (y : ys) where 
     y = x0 `mappend` x1 
     ys = pairs xs' 

data SomeType 

associativeSlowFold = undefined :: SomeType -> SomeType -> SomeType 

data SlowFold = SlowFoldId 
       | SlowFold { getSlowFold :: SomeType } 

instance Monoid SlowFold where 
    mempty = SlowFoldId 
    SlowFoldId `mappend` x = x 
    x `mappend` SlowFoldId = x 
    x0 `mappend` x1 = SlowFold y where 
     y = (getSlowFold x0) `associativeSlowFold` (getSlowFold x1) 
    mconcat = pmconcat 

तुम सच में सबूत सिस्टम आप उन सबूत सहायकों आप का उल्लेख पर भी देखने के लिए चाहते हो सकता है चाहते हैं। प्रोलॉग - तार्किक भाषा है और मुझे नहीं लगता कि यह भी इसके लिए बहुत उपयुक्त है। लेकिन इसका उपयोग कुछ सरल सहायक लिखने के लिए किया जा सकता है। अर्थात। सहयोगीता नियम लागू करने के लिए और देखें कि निम्न स्तर पर समानता प्राप्त करना असंभव है।

Answer 2

पहला समाधान जो मेरे मन में आता है QuickCheck उपयोग कर रहा है।

quickCheck $ \(x, y, z) -> f x (f y z) == f (f x y) z 
quickCheck $ \(x, y) -> f x y == f y x 

जहां f एक ऐसा फ़ंक्शन है जिसका हम परीक्षण कर रहे हैं। यह न तो सहयोगीता और न ही कम्यूटिटी को साबित करेगा; यह एक ब्रूट फोर्स समाधान लिखने का सबसे आसान तरीका है जिसके बारे में आप सोच रहे हैं। क्विक चेक का लाभ यह है कि परीक्षण 'पैरामीटर' चुनने की क्षमता है जो उम्मीदवार परीक्षण कोड के लिए कोने के मामले होंगे।

एक isAssociative आप

isAssociative 
    :: (Arbitrary t, Show t, Eq t) => (t -> t -> t) -> IO() 
isAssociative f = quickCheck $ \(x, y, z) -> f x (f y z) == f (f x y) z 

QuickCheck यादृच्छिक द्वारा परीक्षण मामलों चुनता है के रूप में यह IO में है के रूप में परिभाषित किया जा सकता है के लिए पूछ रहे हैं।