प्रत्यावर्तन

Question

मैं Haskell realization of memoization समझने की कोशिश कर रहा हूँ, लेकिन मैं नहीं मिलता है यह कैसे काम करता साथ Memoization: क्यों 'map'-समारोह तीन पैरामीटर प्राप्त सभी मैं भी समझ में नहीं आता की

memoized_fib :: Int -> Integer 
memoized_fib = (map fib [0..] !!) 
    where fib 0 = 0 
       fib 1 = 1 
       fib n = memoized_fib(n - 2) + memoized_fib(n - 1) 

पहले (समारोह - फिब, सूची [0 ..], और ||), लेकिन दो नहीं, इसे कैसे करना चाहिए।

अपडेट किया गया:

मैं कोड को फिर से लिखने की कोशिश की है, लेकिन अलग अलग परिणाम प्राप्त:

f' :: (Int -> Int) -> Int -> Int 
f' mf 0 = 0 
f' mf 1 = 1 
f' mf n = mf(n - 2) + mf(n - 1) 

f'_list :: [Int] 
f'_list = map (f' faster_f') [0..] 

faster_f' :: Int -> Int 
faster_f' n = f'_list !! n 

क्यों? क्या मेरे तर्क में कोई त्रुटि है?

Answer 1

पहला: हास्केल ऑपरेटर अनुभागों का समर्थन करता है। तो (+ 2)\ x -> x + 2 के बराबर है। इसका अर्थ यह है कि map के साथ अभिव्यक्ति \ x -> map fib [0..] !! x के बराबर है।

दूसरा, यह कैसे काम करता है: यह हास्केल की call-by-need मूल्यांकन रणनीति (इसकी आलस्य) का लाभ उठा रहा है।

प्रारंभ में, map से परिणाम की सूची का मूल्यांकन नहीं किया गया है। फिर, जब आपको कुछ विशेष इंडेक्स प्राप्त करने की आवश्यकता होती है, तो उस बिंदु तक के सभी तत्वों का मूल्यांकन किया जाता है। हालांकि, एक बार तत्व का मूल्यांकन करने के बाद, इसे फिर से मूल्यांकन नहीं किया जाता है (जब तक आप एक ही तत्व का जिक्र कर रहे हों)। यह आपको याद दिलाता है।

असल में, हास्केल की आलसी मूल्यांकन रणनीति में मजबूर मूल्यों को याद रखना शामिल है। यह ज्ञात fib फ़ंक्शन बस उस व्यवहार पर निर्भर करता है।

यहां "मूल्य को मजबूर करना" का अर्थ है एक स्थगित अभिव्यक्ति का मूल्यांकन करना जिसे थंक कहा जाता है। इसलिए सूची मूल रूप से एक सूची के "वादे" के रूप में संग्रहीत की जाती है, और इसे मजबूर करने से यह "वास्तविक" में "वादा" और अधिक मूल्यों के लिए "वादा" हो जाता है। "वाद" केवल थंक्स हैं, लेकिन मुझे उम्मीद है कि यह एक वादा को और अधिक समझ में आता है।

मैं थोड़ा सा सरल बना रहा हूं, लेकिन यह स्पष्ट करना चाहिए कि वास्तविक ज्ञापन कैसे काम करता है।

Answer 2

map यहां तीन पैरामीटर नहीं लेते हैं।

(map fib [0..] !!) 

आंशिक रूप से लागू होता है (स्लाइस) समारोह map fib [0..], एक सूची के साथ (!!), इसके पहले (बाएं हाथ) तर्क के रूप में।

Answer 3

हो सकता है कि यह स्पष्ट लिखा के रूप में बताया गया है:

memoized_fib n = (map fib [0..]) !! n 

तो यह सिर्फ n वें तत्व सूची से ले रहा है, और सूची lazily मूल्यांकन किया जाता है।

यह operator section सामान सामान्य आंशिक अनुप्रयोग के समान है, लेकिन इन्फिक्स ऑपरेटरों के लिए बिल्कुल समान है। वास्तव में, यदि हम !! इन्फ़िक्स ऑपरेटर के बजाय एक नियमित रूप से समारोह के साथ एक ही प्रपत्र लिखते हैं, देखें कि यह कैसे दिखता है:

import Data.List (genericIndex) 

memoized_fib :: Int -> Integer 
memoized_fib = genericIndex (map fib [0..]) 
    where fib 0 = 0 
       fib 1 = 1 
       fib n = memoized_fib(n - 2) + memoized_fib(n - 1)