हास्केल

Question

में संरचनात्मक प्रेरण संरचनात्मक प्रेरण की परिभाषा निम्नलिखित है?

foldr f a (xs::ys) = foldr f (foldr f a ys) xs 

क्या कोई मुझे हास्केल में संरचनात्मक प्रेरण का उदाहरण दे सकता है?

Answer 1

आपने इसे निर्दिष्ट नहीं किया है, लेकिन मुझे लगता है कि :: का अर्थ है सूची सम्मेलन और ++ का उपयोग करें, क्योंकि यह ऑपरेटर हैस्केल में उपयोग किया जाता है। इसे साबित करने के लिए, हम xs पर प्रेरण प्रदर्शन करेंगे। सबसे पहले, हम बताते हैं कि बयान आधार मामला (यानी xs = [])

foldr f a (xs ++ ys) 
{- By definition of xs -} 
= foldr f a ([] ++ ys) 
{- By definition of ++ -} 
= foldr f a ys 

और

foldr f (foldr f a ys) xs 
{- By definition of xs -} 
= foldr f (foldr f a ys) [] 
{- By definition of foldr -} 
= foldr f a ys 

अब

, हम मानते हैं कि प्रेरण परिकल्पना foldr f a (xs ++ ys) = foldr f (foldr f a ys) xsxs के लिए रखती है और पता चलता है कि यह आयोजन करेगा के लिए रखती है सूची x:xs के लिए भी।

foldr f a (x:xs ++ ys) 
{- By definition of ++ -} 
= foldr f a (x:(xs ++ ys)) 
{- By definition of foldr -} 
= x `f` foldr f a (xs ++ ys) 
     ^------------------ call this k1 
= x `f` k1 

और

foldr f (foldr f a ys) (x:xs) 
{- By definition of foldr -} 
= x `f` foldr f (foldr f a ys) xs 
     ^----------------------- call this k2 
= x `f` k2 

अब, हमारा प्रेरण परिकल्पना से, हम जानते हैं कि k1 और k2 बराबर हैं, इसलिए

x `f` k1 = x `f` k2 

इस प्रकार हमारे परिकल्पना साबित।