हैकेल - हाइपरपरेशन (एकरमेन) फ़ंक्शन, टेट्रेशन

Question

मैं हैकेल में एक हाइपरपरेशन फ़ंक्शन लिखने की कोशिश कर रहा हूं।

यह आमतौर पर ackermann(a,b,n) के रूप में लिखा जाता है लेकिन आंशिक अनुप्रयोग उद्देश्यों के लिए मुझे लगता है कि यह n पहले रखना अधिक समझ में आता है। इस तरह के रूप में मैं यह फोन कर रहा हूँ hypOp n a b

प्रपत्र मैं गया है पाया सबसे प्राकृतिक का उपयोग करता है Ao परतों replicate सूचियों इस तरह:

Prelude> replicate 3 5 
[5,5,5] 
Prelude> foldr1 (*) $ replicate 3 5 
125 

गुना इस इसके अलावा हो सकता है करने के लिए समारोह तर्क के आधार पर, mutliplication, घातांक, tetration, आदि

अनौपचारिक अवलोकन:

hypOp 0 a _ = succ a 
hypOp 1 a b = a + b = foldr1 (succ a) (replicate b a) --OFF BY ONE ISSUES, TYPE ISSUES 
hypOp 2 a b = a * b = foldr1 (+) $ replicate b a 
hypOp 3 a b = a^b = foldr1 (*) $ replicate b a 
hypOp 4 a b = = foldr1 (^) 

साहचर्य कारणों मैं im के तहत कर रहा हूँ के लिए दबाव मुझे सही गुना का उपयोग करना चाहिए, जो दुर्भाग्यपूर्ण है क्योंकि बाएं गुना (foldl') के साथ उपलब्ध सख्तता उपयोगी होगी।

अधिकार बनाम बाईं मुद्दा

Prelude> foldl1 (^) $ replicate 4 2 --((2^2)^2)^2 = (4^2)^2 = 16^2 = 256 != 2 tetra 4 
256 
Prelude> foldr1 (^) $ replicate 4 2 --(2^(2^(2^2))) = 2^16 = 65536 == 2 tetra 4 
65536 

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

Prelude> let add a b = foldr1 (\a b -> succ b) $ replicate b a 
Prelude> add 5 4 
8 
Prelude> add 10 5 --always comes out short by one, so i cant build off this 
14 

पहले कुछ n मूल्यों किया im:

:

Prelude> let mul a b = foldr1 (+) $ replicate b a 
Prelude> let exp a b = foldr1 mul $ replicate b a 
Prelude> let tetra a b = foldr1 exp $ replicate b a 
Prelude> let pent a b = foldr1 tetra $ replicate b a 
Prelude> let sixate a b = foldr1 pent $ replicate b a 
Prelude> mul 2 3 --2+2+2 
6 
Prelude> exp 2 3 --2*2*2 
8 
Prelude> tetra 2 3 --2^(2^2) 
16 
Prelude> pent 2 3 --2 tetra (2 tetra 2) 
65536 
Prelude> sixate 2 3 
*** Exception: stack overflow 

मेरे ऊपर दृष्टिकोण के माध्यम से औपचारिक परिभाषा पर प्रयास

hypOp :: Int -> Int -> Int -> Int 
hypOp 0 a b = succ a 
hypOp 1 a b = (+) a b --necessary only bc off-by-one error described above 
hypOp n a b = foldr1 (hypOp $ n-1) (replicate b a) 

अन्य प्रयास दोहराव रिकर्सिव सरणी (किसी भी महत्वपूर्ण तरीके से अलग नहीं):

let arr = array (0,5) ((0, (+)) : [(i, (\a b -> foldr1 (arr!(i-1)) (replicate b a))) | i <- [1..5]]) 
-- (arr!0) a b makes a + b 
-- (arr!1) a b makes a * b, etc. 

तो मेरी सवाल कर रहे हैं ...

1. किसी भी सामान्य सुझाव, अलग appraoches वह समारोह टी के लिए? मैं नहीं कर सकते एक तरह से एक बहुत ही 'जरूरी' शैली जो मेरा इरादा जब Haskell का उपयोग कर और एक मुहावरेदार शैली में कोड करने के लिए कोशिश कर रहा है नहीं है का उपयोग कर के अलावा अतिप्रवाह से बचने के लिए खोजने के लिए प्रतीत
2. कैसे मेरी बंद-एक करके इस मुद्दे से निपटा जा सकता इसलिए मैं succ
3. सख्तता और बाएं बनाम दाएं गुना के साथ बहुत नीचे 'ठीक से' शुरू कर सकता हूं। seq में काम करने का कोई तरीका है? foldr1 के बजाय मैं foldl1' का उपयोग कर सकता हूं और ऊपर वर्णित समस्या से बच सकता हूं?

Answer 1

1. बिंदु 3. देखें हालांकि यह इस तरह से इन आपरेशनों को परिभाषित करने के काम करता है, और आप अतिप्रवाह के बिना यह कर सकते हैं, यह एक बेहद अक्षम दृष्टिकोण है। आपका रन टाइम उत्तर में रैखिक है, क्योंकि आप दोहराए गए जोड़ को समाप्त करते हैं।

2. कारण आप ऑफ-बाय-वन प्राप्त कर रहे हैं मूल रूप से क्योंकि आप का उपयोग foldr f के बजाय पहचान के साथ कर रहे हैं।

   foldr (+) 0 [a, a, a] = a + (a + (a + 0))) 
   foldr1 (+) [a, a, a] = a + (a + a) 
   

   सूचना वहाँ foldr1 के मामले में + में से एक कम आवेदन है।

3. (^) पर तर्कों के क्रम को बदलने के बारे में कैसे? इस तरह, आप एक को छोड़ दिया गुना का उपयोग कर सकते हैं:

   Prelude Data.List> foldl1 (flip (^)) $ replicate 4 2 
   65536 
   

   अब आप सख्त संस्करण का उपयोग कर सकते हैं foldl1'। यह अब बहती नहीं है, लेकिन यह निश्चित रूप से बेहद अक्षम है।