सूचियों का उपयोग करके रिकर्सन - हास्केल

Question

मैं एक रिकर्सिव फ़ंक्शन लिखने की कोशिश कर रहा हूं जो एक सूची के रूप में पूर्णांक की सूची वाली एक सूची लेगा और एक प्रकार का टुपल ([Int], Int) लौटाएगा। ([इंट] इंट)

यह एक "बोर्ड खेल" जहाँ आप एक बोर्ड के साथ आपूर्ति की जाती है के लिए है:

[[5,4,3,8,6], 
    [0,2,1,0,7], 
    [0,1,9,4,3], 
    [2,3,4,0,9]] 

यह 4 पंक्तियों और 5 कॉलम के साथ एक बोर्ड होगा। सूची के अंदर की संख्या "सिक्के मूल्य" हैं। इस बोर्ड गेम का उद्देश्य सिक्कों को इकट्ठा करने के लिए सूची के शीर्ष से नीचे जाना होगा। आप शीर्ष पंक्ति से किसी भी स्थिति में शुरू करने और नीचे जाने के लिए सक्षम हैं, आप सीधे नीचे या तिरछे बाएं या दाएं जा सकते हैं। आप वह रास्ता चाहते हैं जो आपको सबसे बड़ा सिक्का मूल्य प्रदान करेगा।

मैंने पहला फ़ंक्शन बनाया है जहां आप पथों की सूची इनपुट करते हैं [([Int], Int)] और यह अधिकतम सिक्का मान के साथ पथ ([Int], Int) देता है।

अब मुझे वास्तव में पथों की सूची जेनरेट करने के लिए एक फ़ंक्शन बनाने की आवश्यकता है जिसे मैं पहले फ़ंक्शन में इनपुट करूंगा।

मुझे पता है कि मुझे रिकर्सन का उपयोग करना होगा। मैं बोर्ड (जैसे ऊपर एक) और एक प्रारंभिक कॉलम इनपुट करेगा। मुझे कॉलम नंबर लेना होगा और फिर सभी संभावित पथों की एक सूची बनाना होगा। यदि मैं कॉलम नंबर से शुरू करता हूं, तो मेरे अगले संभावित चरण स्थिति (अगली पंक्ति में) हैं - समान कॉलम संख्या, कॉलम संख्या -1 और कॉलम num +1। जब तक मैं नीचे तक नहीं पहुंच जाता तब तक मुझे इसे फिर से कॉल करने की आवश्यकता होगी।

मैं इन पथ चरणों को संग्रहीत करने में सक्षम कैसे होगा और फिर सभी संभव पथों की अंतिम सूची को स्टोर कर सकता हूं?

([Int], Int) - [Int] सूची/कॉलम संख्याओं में पंक्ति है या पंक्तियां और Int सिक्का मान है।

मैं हैकेल के लिए नया हूं और जब मैं समझता हूं कि मुझे क्या करना है, तो कोड लिखना वाकई मुश्किल है।

Answer 1

आप नहीं "स्टोर" मुहावरेदार कार्यात्मक कोड में कुछ चर में मध्यवर्ती मूल्यों से करते हैं। इसके बजाय, आप उन्हें एक संचय पैरामीटर के रूप में रखते हैं जिसे आप फ़ोल्डर जैसे फ़ंक्शन का उपयोग करके पास करते हैं।

http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:foldr

Answer 2

मुझे लगता है मैं (आसानी से) यह एक करने के लिए another question के लिए मेरा उत्तर अनुकूल करने के लिए की स्थिति में हूँ। मैंने अनुमत सूचकांक संयोजन सूचीबद्ध किए और बोर्ड को मैप किया। (पैट के comment मुझे index_combinations सुधारने में मदद)

* मुख्य>: लोड "new1.hs"
[1 के 1] मुख्य (new1.hs, व्याख्या)
ठीक है, मॉड्यूल लोड संकलन: मुख्य।
* मुख्य> परिणाम
([8,7,4,9], 28)
* मुख्य> पथ
[3,4,3,4]

import Data.List 
import Data.Ord 
import Data.Maybe 

r = [[5,4,3,8,6], 
    [0,2,1,0,7], 
    [0,1,9,4,3], 
    [2,3,4,0,9]] 

r1 = r !! 0 
r2 = r !! 1 
r3 = r !! 2 
r4 = r !! 3 

index_combinations = 
    [[a,b,c,d] | a <- [0..4], b <- [max 0 (a-1)..min 4 (a+1)], 
    c <- [max 0 (b-1)..min 4 (b+1)], d <- [max 0 (c-1)..min 4 (c+1)]] 

mapR xs = [r1 !! (xs !! 0), r2 !! (xs !! 1), 
      r3 !! (xs !! 2), r4 !! (xs !! 3)] 

r_combinations = map mapR index_combinations 
r_combinations_summed = zip r_combinations $ map (foldr (+) 0) r_combinations 

result = maximumBy (comparing snd) r_combinations_summed 
path = index_combinations !! fromJust (elemIndex result r_combinations_summed) 

Answer 3

यदि आप एक उदाहरण के रूप grid(userguide) यहाँ मेरी पैकेज का उपयोग आरंभ करने के लिए में रुचि रखते। (और आप इसे का उपयोग नहीं करना चाहते हैं तो आपको स्रोत कोड उपयोगी में से कुछ मिल सकता है।)

4 पंक्तियों और 5 कॉलम के साथ एक ग्रिड बनाएं।

λ> :m + Math.Geometry.Grid 
λ> let g = rectSquareGrid 4 5 
λ> indices g 
[(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(1,3),(2,0),(2,1),(2,2),(2,3),(3,0),(3,1),(3,2),(3,3),(4,0),(4,1),(4,2),(4,3)] 

हम ग्रिड पदों के लिए "सिक्का मूल्यों" मैप करने के लिए सक्षम होना चाहते हैं, तो हम एक GridMap पैदा हो जाएगी।

λ> :m + Math.Geometry.GridMap 
λ> let m = lazyGridMap g [5,4,3,8,6,0,2,1,0,7,0,1,9,4,3,2,3,4,0,9] 
λ> m 
lazyGridMap (rectSquareGrid 4 5) [5,4,3,8,6,0,2,1,0,7,0,1,9,4,3,2,3,4,0,9] 
λ> toList m 
[((0,0),5),((0,1),4),((0,2),3),((0,3),8),((1,0),6),((1,1),0),((1,2),2),((1,3),1),((2,0),0),((2,1),7),((2,2),0),((2,3),1),((3,0),9),((3,1),4),((3,2),3),((3,3),2),((4,0),3),((4,1),4),((4,2),0),((4,3),9)] 

हम ग्रिड, में लेकिन आपके आवेदन के लिए किसी भी सेल के पड़ोसियों पता कर सकते हैं, हम एक समस्या का एक सा में चलाने: मेरे RectSquareGrid प्रकार विकर्ण चालें अनुमति नहीं है।

λ> neighbours (1,2) m 
[(0,2),(1,3),(2,2),(1,1)] 

अब, मैं Grid के एक नए प्रकार है कि आपके आवश्यकताओं को पूरा करेगा बनाने के लिए खुशी होगी। वैकल्पिक रूप से, आप अपने खुद के समारोह लिख सकता है जो विकर्ण पड़ोसियों शामिल होंगे:

λ> let allowedMoves (x, y) g = filter (`inGrid` g) [(x+1,y-1), (x+1,y), (x+1,y+1)] 
λ> allowedMoves (1,2) m 
[(2,1),(2,2),(2,3)] 

:

λ> let neighbours2 (x, y) g = filter (`inGrid` g) [(x-1,y-1), (x-1,y), (x-1,y+1), (x,y-1), (x,y+1), (x+1,y-1), (x+1,y), (x+1,y+1)] 
λ> neighbours2 (1,2) m 
[(0,1),(0,2),(0,3),(1,1),(1,3),(2,1),(2,2),(2,3)] 

लेकिन आप केवल नीचे की ओर ले जाता है की अनुमति देता है में रुचि रखते हैं, या तो सीधे नीचे या विकर्ण हैं, तो यहाँ एक अधिक उपयोगी समारोह है

तो अब हम एक ऐसा फ़ंक्शन लिख सकते हैं जो आपको किसी दिए गए इंडेक्स से ग्रिड की निचली पंक्ति तक सभी संभावित पथ प्रदान करता है।

allPathsFrom a g | fst a == fst (size g) = [[a]] 
       | otherwise    = Prelude.map (a:) xs 
    where xs = concatMap (\x -> allPathsFrom x g) ys 
     ys = allowedMoves a g 

उदाहरण के लिए:

λ> allPathsFrom (0,1) m 
[[(0,1),(1,0),(2,0),(3,0),(4,0)],[(0,1),(1,0),(2,0),(3,0),(4,1)],[(0,1),(1,0),(2,0),(3,1),(4,0)],[(0,1),(1,0),(2,0),(3,1),(4,1)],[(0,1),(1,0),(2,0),(3,1),(4,2)],[(0,1),(1,0),(2,1),(3,0),(4,0)],[(0,1),(1,0),(2,1),(3,0),(4,1)],[(0,1),(1,0),(2,1),(3,1),(4,0)],[(0,1),(1,0),(2,1),(3,1),(4,1)],[(0,1),(1,0),(2,1),(3,1),(4,2)],[(0,1),(1,0),(2,1),(3,2),(4,1)],[(0,1),(1,0),(2,1),(3,2),(4,2)],[(0,1),(1,0),(2,1),(3,2),(4,3)],[(0,1),(1,1),(2,0),(3,0),(4,0)],[(0,1),(1,1),(2,0),(3,0),(4,1)],[(0,1),(1,1),(2,0),(3,1),(4,0)],[(0,1),(1,1),(2,0),(3,1),(4,1)],[(0,1),(1,1),(2,0),(3,1),(4,2)],[(0,1),(1,1),(2,1),(3,0),(4,0)],[(0,1),(1,1),(2,1),(3,0),(4,1)],[(0,1),(1,1),(2,1),(3,1),(4,0)],[(0,1),(1,1),(2,1),(3,1),(4,1)],[(0,1),(1,1),(2,1),(3,1),(4,2)],[(0,1),(1,1),(2,1),(3,2),(4,1)],[(0,1),(1,1),(2,1),(3,2),(4,2)],[(0,1),(1,1),(2,1),(3,2),(4,3)],[(0,1),(1,1),(2,2),(3,1),(4,0)],[(0,1),(1,1),(2,2),(3,1),(4,1)],[(0,1),(1,1),(2,2),(3,1),(4,2)],[(0,1),(1,1),(2,2),(3,2),(4,1)],[(0,1),(1,1),(2,2),(3,2),(4,2)],[(0,1),(1,1),(2,2),(3,2),(4,3)],[(0,1),(1,1),(2,2),(3,3),(4,2)],[(0,1),(1,1),(2,2),(3,3),(4,3)],[(0,1),(1,2),(2,1),(3,0),(4,0)],[(0,1),(1,2),(2,1),(3,0),(4,1)],[(0,1),(1,2),(2,1),(3,1),(4,0)],[(0,1),(1,2),(2,1),(3,1),(4,1)],[(0,1),(1,2),(2,1),(3,1),(4,2)],[(0,1),(1,2),(2,1),(3,2),(4,1)],[(0,1),(1,2),(2,1),(3,2),(4,2)],[(0,1),(1,2),(2,1),(3,2),(4,3)],[(0,1),(1,2),(2,2),(3,1),(4,0)],[(0,1),(1,2),(2,2),(3,1),(4,1)],[(0,1),(1,2),(2,2),(3,1),(4,2)],[(0,1),(1,2),(2,2),(3,2),(4,1)],[(0,1),(1,2),(2,2),(3,2),(4,2)],[(0,1),(1,2),(2,2),(3,2),(4,3)],[(0,1),(1,2),(2,2),(3,3),(4,2)],[(0,1),(1,2),(2,2),(3,3),(4,3)],[(0,1),(1,2),(2,3),(3,2),(4,1)],[(0,1),(1,2),(2,3),(3,2),(4,2)],[(0,1),(1,2),(2,3),(3,2),(4,3)],[(0,1),(1,2),(2,3),(3,3),(4,2)],[(0,1),(1,2),(2,3),(3,3),(4,3)]] 

ध्यान दें कि जब से GridMap रों भी कर रहे हैं Grid रों, हम m या g पर ऊपर सभी कार्यों के आह्वान कर सकते हैं।

λ> allPathsFrom (0,1) m 

अगर तुम मुझे चाहते हैं मेरे grid पैकेज के लिए एक ग्रिड विकर्ण चाल की इजाजत दी जोड़ने के लिए (nualeargais यानी डॉट पर एमी) मेरे जानते हैं।