हास्केल: बिना किसी स्टैक ओवरफ्लो

Question

हास्केल के लिए नौसिखिया के रूप में एक फ़ंक्शन दोहराएं, मैं एक फ़ंक्शन (उदा। लॉजिस्टिक मैप) को बड़ी संख्या में फिर से चलाने की कोशिश कर रहा हूं। एक अनिवार्य भाषा में यह एक साधारण लूप होगा, हालांकि हास्केल में मैं स्टैक ओवरफ़्लो के साथ समाप्त होता हूं। पुनरावृत्तियों कोड काम करता है की एक छोटी संख्या के लिए

main = print $ iter 1000000 

f x = 4.0*x*(1.0-x) 

iter :: Int -> Double 
iter 0 = 0.3 
iter n = f $ iter (n-1) 

, लेकिन एक लाख पुनरावृत्तियों के लिए मैं एक ढेर अंतरिक्ष अतिप्रवाह मिलती है:: इस कोड उदाहरण के लिए ले लो

Stack space overflow: current size 8388608 bytes. 
Use `+RTS -Ksize -RTS' to increase it. 

मैं नहीं समझ सकता क्यों होता है। पूंछ रिकर्सन ठीक होना चाहिए। शायद समस्या आलसी मूल्यांकन है। मैंने विभिन्न पदों पर $! या seq डालने से सख्त मूल्यांकन को मजबूर करने के कई तरीकों से प्रयोग किया, लेकिन कोई सफलता नहीं मिली।

एक समारोह को फिर से चलाने के लिए हास्केल तरीका क्या होगा?

मैं संबंधित पोस्ट से सुझाव की कोशिश की है: here या here, लेकिन मैं हमेशा पुनरावृत्तियों की एक बड़ी संख्या है, जैसे, main = print $ iterate f 0.3 !! 1000000 के लिए stackoverflow के साथ समाप्त हो गया।

Answer 1

समस्या यह है कि अपनी परिभाषा

iter :: Int -> Double 
iter 0 = 0.3 
iter n = f $ iter (n-1) 

की कोशिश करता गलत दिशा में मूल्यांकन करने के लिए है। कुछ ही कदम के लिए यह खुलासा, हम

iter n = f (iter (n-1)) 
     = f (f (iter (n-2))) 
     = f (f (f (iter (n-3)))) 
     ... 

प्राप्त करने और iter 1000000 से iter 0 करने के लिए पूरे कॉल स्टैक से पहले कुछ भी मूल्यांकन किया जा सकता का निर्माण किया जाना है। यह सख्त भाषा में समान होगा। आपको इसे व्यवस्थित करना होगा ताकि मूल्यांकन का हिस्सा आवर्ती से पहले हो सके। मामले में संकलक उन्हें पहले से ही नहीं जोड़ता है - - यह लेने वाली ढेर के बिना सुचारू रूप से संचालित कर देगा हमेशा की तरह, एक संग्रह पैरामीटर की तरह

iter n = go n 0.3 
    where 
    go 0 x = x 
    go k x = go (k-1) (f x) 

तो कठोरता एनोटेशन जोड़ने के लिए है।

iterate संस्करण में आपके iter जैसी ही समस्या है, केवल कॉल स्टैक को आपके अंदर के बजाय अंदरूनी के अंदर बनाया गया है। लेकिन चूंकि iterate अपने कॉल-ढेर के अंदर से बाहर, iterate की एक सख्त संस्करण (या एक खपत पैटर्न जहां पहले पुनरावृत्तियों से पहले मजबूर हैं) समस्या का हल, बनाता है

iterate' :: (a -> a) -> a -> [a] 
iterate' f x = x `seq` (x : iterate' f (f x)) 

समस्या के बिना iterate' f 0.3 !! 1000000 गणना करता है।