haskell - hyperoperation (ackermann) function, tetration

Question

I'm trying to write a hyperoperation function in haskell.

It's usually wrritten as ackermann(a,b,n) but for partial application purposes I think it makes more sense to put n first. As such I'm calling it hypOp n a b

The form I've found most natural uses folds ao replicate lists like this:

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

Depending on the function argument to the fold this can be addition, mutliplication, exponentiation, tetration, etc.

Informal Overview:

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

For associative reasons I am under the impression I must use right folds, which is unfortunate because the strictness available with left folds (foldl') would be useful.

Right vs. left folds issue

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

I get an off-by-one issue when i 'start' a the very beginning with successor function. so instead im using (+) as the function for my base fold

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

First few n values, done 'manually':

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

My attempt at formal definitions thru above approach:

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)

Other attemp twith recursive array (not different in any significant way):

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.

So my questions are...

1. Any general suggestions, different appraoches to t he function? I cant seem to find a way to avoid overflows except for using a very 'imperative' style which is not my intention when using haskell and trying to code in an idiomatic style
2. How my off-by-one issue can be dealt with so I can start 'properly' at the very bottom with succ
3. Strictness and left vs. right folds. Is there a way to work in seq? Some way that I can use foldl1' instead of foldr1 and avoid the problem described above?

Answer 1

1. See point 3. Although it works to define these operations in this way, and you can do it without overflows, it is an extremely inefficient approach. Your run time is linear in the answer, because you end up doing repeated addition.

2. The reason why you're getting the off-by-one is basically because you're using foldr1 f instead of foldr f with an identity.

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

   Notice there is one less application of + in the case of foldr1.

3. How about simply changing the order of arguments to (^)? That way, you can use a left fold:

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

   Now you can use the strict version, foldl1'. It no longer overflows, but it is of course extremely inefficient.