haskell - hyperoperation（ackermann）函數，tetration

Question

我正在嘗試在haskell中編寫hyperoperation函數。

它通常被認爲是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，冪，迭代冪次等

非正式概述：

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值，做「手動」：

：

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到t他的功能？我似乎找不到一種方法來避免溢出，除非使用非常「勢在必行」的風格，這在使用哈斯克爾並嘗試以慣用風格​​編碼時並不是我的意圖。
2. 我可以如何處理我的錯誤問題所以我可以在最底部開始'正確'succ
3. 嚴格性和左側與右側褶皺。有沒有在seq中工作的方法？有些方法可以使用foldl1'而不是foldr1並避免上述問題？

Answer 1

1. 看點3.雖然工作在這種方式來定義這些操作，你可以不用溢出，這是一個非常低效的方法。你的運行時間在答案中是線性的，因爲你最終會重複添加。

2. 你之所以得到一個一個的原因基本上是因爲你使用foldr1 f而不是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'。它不再溢出，但它當然非常低效。