अंतरिक्ष GHC दुभाषिया में केवल विशेष मामलों में रिसाव जब कर रही: concat <some list> !! n

Question

मैं concat के अपने खुद के संस्करण, myConcat को परिभाषित:

module Eh where 

myConcat []   = [] 
myConcat ([]:os)  = myConcat os 
myConcat ((x:xs):os) = x : myConcat (xs:os) 

(!!!) :: [a] -> Int -> a 
xs  !!! n | n < 0 = error "negative index" 
[]  !!! _   = error "index too large" 
(x:_) !!! 0   = x 
(_:xs) !!! n   = xs !!! (n-1) 

अगर मैं GHC दुभाषिया में myConcat <some huge list> !! n करते हैं, यह 300MB/s पर मेरी स्मृति चुरा लेता है, और मैं इसे मारने के लिए इससे पहले कि यह OOM बुलाने कर सकते हैं हत्यारा। यहां ध्यान दें कि मैं Eh को "व्याख्या" के रूप में लोड करता हूं, मैं इसे लोड करने से पहले संकलित नहीं करता हूं।

 
code run in the GHC interpreter  space leak? 
myConcat (repeat [1,2,3,4]) !! (10^8) Yes 
concat (repeat [1,2,3,4]) !! (10^8) No 
myConcat (repeat [1,2,3,4]) !!! (10^8) No 
concat (repeat [1,2,3,4]) !!! (10^8) No 

अब अगर मैं संकलन Eh (ghc --make -O2 Eh.hs), और फिर दुभाषिया में लोड और इन परीक्षणों को फिर से चलाने, उनमें से कोई अंतरिक्ष रिसाव। वैसे ही अगर मैं दुभाषिया में उन्हें चलाने के बजाय प्रत्येक टेस्ट केस संकलित करता हूं।

क्या चल रहा है?

---

मैं जीएचसी 6.12.3 चला रहा हूं।

Answer 1

यहां मुद्दा यह कठोरता है। हास्केल में मूल्यांकन गैर-सख्त है, इसलिए गणना आमतौर पर तभी होती है जब उनके परिणामों की वास्तव में आवश्यकता होती है। इसके बजाए, एक तथाकथित थंक बनाया गया है जो अभी तक किए गए गणना का प्रतिनिधित्व करता है।

कुछ मामलों में संकलक लेकिन पता लगा सकते हैं कि गणना का परिणाम वैसे भी आवश्यकता होगी और इसलिए वास्तविक गणना द्वारा Thunks के निर्माण बदल देता है।

Haskell Wiki शायद इस बेहतर बताते हैं।

अपने myConcat फ़ंक्शन को ठीक करने के लिए आपको यह सुनिश्चित करना होगा कि यह सख्त मूल्यांकन को मैन्युअल रूप से मजबूर कर लाखों हिस्सों को नहीं बनाये। एक (नहीं बहुत सुंदर लग रही) ऐसा करने का तरीका हो सकता है:

myConcat []   = [] 
myConcat ([]:os)  = myConcat os 
myConcat ((x:xs):os) = ((:) $! x) myConcat (xs:os)