haskell - función de hiperoperación (ackermann), tetration

Question

Estoy tratando de escribir una función de hiperoperación en haskell.

Por lo general se escribe como ackermann(a,b,n), pero para fines de aplicación parcial, creo que tiene más sentido poner n primero. Como tal, estoy llamando hypOp n a b

La forma usos más naturales que se encuentran He pliegues ao replicate listas de la siguiente manera:

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

Dependiendo del argumento de la función al redil esto puede ser, además, mutliplication, exponenciación, tetración, etc.

general informal:

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

Por razones asociativos tengo la im Pression Debo usar pliegues derechos, lo cual es desafortunado porque la rigurosidad disponible con pliegues izquierdos (foldl') sería útil.

derecha vs. izquierda pliega tema

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 

consigo un problema off-by-one cuando i 'Inicio' un principio con la función sucesor. así que en vez im usando (+) como la función de mi base de pliegue

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 

primeros pocos n valores, hecho 'manualmente':

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 

Mi intento de definiciones formales thru enfoque anterior:

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) 

Otro intento de matriz recursiva (no diferente de manera significativa):

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. 

Así que mis preguntas son ...

1. Cualquier sugerencia generales, diferentes appraoches a L a función? No puedo encontrar una manera de evitar desbordamientos a excepción de utilizar un estilo muy 'imperativo' que no es mi intención cuando uso Haskell y trato de codificar en un estilo idiomático
2. Cómo se puede tratar mi problema de uno a uno así que puedo comenzar "correctamente" en la parte inferior con succ
3. Estricto y pliegues izquierdos y derechos. ¿Hay alguna manera de trabajar en seq? ¿De alguna forma puedo usar foldl1' en lugar de foldr1 y evitar el problema descrito anteriormente?

Answer 1

1. Véase el punto 3. A pesar de que trabaja para definir estas operaciones de esta manera, y usted puede hacerlo sin desbordamientos, es un enfoque extremadamente ineficiente. Su tiempo de ejecución es lineal en la respuesta, porque termina haciendo adiciones repetidas.

2. La razón por la que está obteniendo el dispositivo de apagado es básicamente porque está utilizando foldr1 f en lugar de foldr f con una identidad.

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

   cuenta de que hay una menor aplicación de + en el caso de foldr1.

3. ¿Qué tal, simplemente cambiando el orden de los argumentos a (^)? De esta manera, se puede utilizar un pliegue izquierda:

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

   Ahora puede utilizar la versión estricta, foldl1'. Ya no se desborda, pero por supuesto es extremadamente ineficiente.