haskell - 超操作（ackermann）函数，四定

Question

我正在尝试用 haskell 编写一个超级操作函数。

它通常写成 ackermann(a,b,n) 但出于部分应用的目的，我认为将 n 放在前面更有意义。因此，我将其称为 hypOp na b

我发现最自然的形式使用折叠 ao replicate 列表，如下所示：

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

根据折叠的函数参数，这可以是加法、乘法、求幂、四乘等。

非正式概述：

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 (^)

出于联想原因，我的印象是我必须使用右折叠，这是不幸的，因为左折叠 (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. 任何一般性建议，对该功能的不同方法？我似乎无法找到一种方法来避免溢出，除了使用非常“命令式”的风格，这不是我在使用 haskell 并尝试以惯用风格​​编码时的意图
2. 如何处理我的逐一问题，以便我可以从最底部开始“正确”地使用 succ
3. 严格性以及左折叠和右折叠。有没有办法在 seq 中工作？我可以使用 foldl1' 而不是 foldr1 并避免上述问题吗？

Answer 1

1. 请参见第 3 点。虽然可以通过这种方式定义这些操作，并且可以在没有溢出的情况下完成，但这是一种效率极低的方法。您的运行时间在答案中是线性的，因为您最终会进行重复的加法。

2. 您获得差一的原因基本上是因为您使用带有身份的 foldr1 f 而不是 foldr f 。

   foldr (+) 0 [a, a, a] = a + (a + (a + 0)))
   折叠r1 (+) [a, a, a] = a + (a + a)
   

   请注意，在 foldr1 的情况下，+ 的应用少了一次。

3. 简单地将参数的顺序更改为(^)怎么样？这样，您就可以使用左折叠：

   Prelude Data.List> Foldl1 (翻转 (^)) $ 复制 4 2
   65536
   

   现在您可以使用严格版本foldl1'。它不再溢出，但效率当然极低。