रिकर्सन

Question

को सरल बनाने के लिए Idiomatic Haskell कोड मुझे foo n = maximumBy (comparing p) [1..n] की गणना करने की आवश्यकता है, जहां p :: Int -> Int धीमा है। लेकिन मुझे पता है कि p n < n सभी n > 0 के लिए और इस गणना का उपयोग निम्न गणना को निम्न तरीके से करने के लिए करना चाहते हैं: n से के साथ p x की गणना करें, वर्तमान अधिकतम को याद करते हुए। एक बार जब मैं x तक पहुंचता हूं तो वर्तमान अधिकतम के बराबर या बराबर, मुझे पता है कि यह अधिकतम वैश्विक होना चाहिए और मैं कर रहा हूं।

तो मेरी प्रयास इस तरह दिखता है:

foo n = go (0, 0) n where 
    go (c, _) 1 = c 
    go (c, c') !x = if c' >= x then c else go (c2, c'2) (x-1) where 
     x' = p x 
     (c2, c'2) = if c' >= x' then (c, c') else (x, x') 

यह काम करता है, लेकिन बहुत मुहावरेदार नहीं लगती है। तो मैं एक और अधिक सुरुचिपूर्ण समाधान की तलाश में हूं। क्या आपके पास सुझाव हैं?

Answer 1

आप पैटर्न अगर के उपयोग को कम करने के लिए मिलान का उपयोग कर सकते हैं ... फिर ... किसी और
एक और चाल अपने चर के लिए एक नंबर देने के लिए, यह आप शुरू करने के मामले को याद करने के var0 और के लिए अनुमति है अन्य रिकर्सिव कॉल के बाद आप एक निसर var
अंतिम नोट, आपके पास है यदि उसी फॉर्म की भविष्यवाणी के बाद समान मूल्य लौटा रहा है और उसी वातावरण को साझा करने के बाद हो सकता है तो आप उन्हें एक साथ समूहित कर सकते हैं।

foo n0 = go (0, 0) n0 
    where 
    go (x, y) n 
     | (n == 1) || (y >= n) = x 
     | y < (p n) = go (n, (p n)) (n-1) 
     | otherwise = go (x, y) (n-1) 

---

पुनर्लेखन खाते टिप्पणी को ध्यान में रखकर,

foo n0 = go 0 0 n0 
    where 
    go x y n 
     | (n == 1) || (y >= n) = x 
     | pn > y    = go n pn (n-1) 
     | otherwise    = go x y (n-1) 
      where 
      pn = p n 

Answer 2

ठीक है, तो मुझे देखने दो कि क्या मैंने अपने मस्तिष्क को इस तरीके से लपेट लिया है ... आप कह रहे हैं कि p n < n सभी रोचक n के लिए। और x = n to 1 के लिए p x की गणना करना चाहते हैं, x अब तक के सबसे बड़े p x से कम हो गया है?

ठीक है, ऐसा लगता है कि आप सभी p x को आलसी सूची के रूप में गणना कर सकते हैं। अब जब तक आप जो खोज रहे हैं उसे ढूंढने तक इस सूची को स्कैन करने में समस्या कम हो जाती है। मैं takeWhile का सुझाव दूंगा, सिवाय इसके कि हमें मौजूदा अधिकतम खोजने के लिए गुना की आवश्यकता भी है। हम्म, शायद हम प्रत्येक मूल्य को चल रहे अधिकतम के साथ जोड़ सकते हैं?

foo n = 
    let 
    ps = [ p x | x <- [n, n-1 .. 1] ] 
    qs = fold (\ px' (px, maxPX) -> (px', maxPX `max` px')) ps 
    in last . takeWhile (\ (px, maxPX) -> px >= maxPX) qs 

या इसी तरह की तरह?