Haskell - Hyperoperation (Ackermann), Tetation

Question

I am trying to write a hyperpositional function in haskell.

It is usually written as ackermann(a,b,n) , but for partial use, I think it makes sense to put n first. Therefore i call it hypOp nab

In the form I found in the most natural way, dumps ao replicate lists as follows:

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

Depending on the argument of the function from the fold, this can be addition, mutual assimilation, exponentiation, tetration, etc.

Informal review:

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

For associative reasons, I get the impression that I have to use the correct folds, which is unsuccessful, because the rigor available with the left folds ( foldl' ) would be useful.

The problem with the left folds

 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 the question “one by one” when I “start” the very beginning with a successor function. so instead of im use (+) as a function for my base crease

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

The first few n values ​​made by hand:

 Prelude> let mul ab = foldr1 (+) $ replicate ba Prelude> let exp ab = foldr1 mul $ replicate ba Prelude> let tetra ab = foldr1 exp $ replicate ba Prelude> let pent ab = foldr1 tetra $ replicate ba Prelude> let sixate ab = foldr1 pent $ replicate ba 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 through the approach described above:

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

Other recursive attemp arrays (it doesn't matter in any significant way):

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

So my questions are ...

• Any general suggestions, different grades to make it work? I can’t find a way to avoid overflow except using a very “imperative” style, which is not my intention when using haskell and trying to code in idiomatic style.
• How my problem individually can be solved, so I can start "right" at the very bottom with succ
• Strictness and left and right folds. Is there any way to work in seq ? Somehow I can use foldl1' instead of foldr1 and avoid the problem described above?

Answer 1

• See point 3. Although it works to define these operations in this way, and you can do it without overflow, this is an extremely inefficient approach. Your runtime is linear in the answer because you are doing the re-add.

• The reason you get "one by one" is mainly because you use foldr1 f instead of foldr f with id.

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

  Note that in the case of foldr1 there is one lesser use of + .

• How to just change the order of the arguments to (^) ? So you can use the left fold:

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

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