हास्केल: foldr foldr1 बनाम

Question

यदि मैं यह डालने समारोह है:

foldr insert [] [1,19,-2,7,43] 

लेकिन इस:

insert x []  = [x] 
insert x (h:t) 
    | x <= h  = x:(h:t) 
    | otherwise = h:(insert x t) 

यह एक क्रमबद्ध सूची का उत्पादन

foldr1 insert [1,19,-2,7,43] 

पैदा करता है 'का निर्माण नहीं कर सकते अनंत प्रकार: a0 = [a0] '

मैं उलझन में हूं कि दूसरी कॉल क्यों काम नहीं कर सकती है।

मैं foldr और foldr1 दोनों के लिए परिभाषाओं पर ध्यान दिया है और साधारण अंकगणित कार्यों के साथ दोनों का पता लगाया है, लेकिन मैं अभी भी क्यों दूसरी कॉल विफल रहता है के लिए एक स्पष्ट विवरण के साथ नहीं आ सकती।

Answer 1

क्योंकि foldr1 यह करने के लिए कोशिश कर रहा है:

insert 43 -7 

जो असफल हो जायेगी।

Answer 2

foldr1 का प्रकार (a -> a -> a) -> [a] -> a है, यानी इस फ़ंक्शन के तर्क और परिणाम एक ही प्रकार के हैं। हालांकि, insert में Ord a => a -> [a] -> [a] टाइप किया गया है। foldr1 insert के लिए अच्छी तरह से टाइप किया जा रहा है, a और [a] एक ही प्रकार का होना चाहिए।

लेकिन इसका मतलब यह होगा कि a == [a] == [[a]] == [[[a]]] == ..., यानी a असीमित कई सूचियों का एक प्रकार है।

Answer 3

चलो कुछ प्रकार के हस्ताक्षर देखें।

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr1 :: (a -> a -> a) ->  [a] -> a 

दोनों मामलों में, पहला तर्क दो तर्कों का एक कार्य है।

• foldr1 के लिए, इन दो तर्क एक ही प्रकार होना आवश्यक है (और परिणाम इस प्रकार भी है)
foldr के लिए
• , इन दो तर्क विभिन्न प्रकार हो सकता है (और परिणाम दूसरे के रूप में एक ही प्रकार है तर्क)

अपने insert का प्रकार क्या है?

Answer 4

समस्या पीछा कर रहा है:

1. परिणाम के लिए insert 43 []
2. परिणाम insert 7 result को
3. और इतने

इस पर स्पष्ट रूप से सेट सेट:

foldr इस तरह से करना होगा काम करता है।insert -2 result

आदि

जो निश्चित रूप से गलत है करने के लिए सेट

1. परिणाम insert 7 43
2. परिणाम पर सेट:

   foldr1 जबकि निम्न कार्य करने की कोशिश करेंगे। आप देख सकते हैं, foldr1 को ऑपरेशन के लिए तर्क एक ही प्रकार के होने की आवश्यकता है, जो insert के मामले में नहीं है।

Answer 5

मुझे यहां दिए गए प्रकार-आधारित उत्तरों पसंद हैं, लेकिन मैं यह भी एक परिचालन देना चाहता हूं कि हम यह क्यों टाइप करना चाहते हैं। के foldr1 के स्रोत लेने के साथ शुरू करने के लिए करते हैं:

foldr1   :: (a -> a -> a) -> [a] -> a 
foldr1 _ [x] = x 
foldr1 f (x:xs) = f x (foldr1 f xs) 

अब, चलो अपने कार्यक्रम चलाने की कोशिश करते हैं।

foldr1 insert [1,19,-2,7,43] 
= { list syntax } 
foldr1 insert (1:[19,-2,7,43]) 
= { definition of foldr1 } 
insert 1 (foldr1 insert [19,-2,7,43]) 
= { three copies of the above two steps } 
insert 1 (insert 19 (insert (-2) (insert 7 (foldr1 insert [43])))) 
= { definition of foldr1 } 
insert 1 (insert 19 (insert (-2) (insert 7 43))) 

... व्हाउप्स! वह insert 7 43 कभी काम नहीं करेगा। =)