haskell - hyperoperation (ackermann) fonction, tetration

Question

J'essaye d'écrire une fonction d'hyperopération en haskell.

Il est généralement écrit comme ackermann(a,b,n) mais pour des applications partielles, je pense qu'il est plus logique de mettre d'abord n. En tant que tel je l'appeler hypOp n a b

La forme que j'ai trouvé des utilisations les plus naturelles plis ao replicate listes comme ceci:

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

Selon l'argument de fonction à la fois cela peut être plus, mutliplication, exponentiation, tétration, etc.

Vue d'ensemble informel:

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

Pour des raisons associatives, je suis sous le im Je dois utiliser des plis droits, ce qui est regrettable car la rigueur disponible avec les plis gauches (foldl') serait utile.

droite vs gauche plis question

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 

je reçois un arrêt par un problème quand je commence 'un le début avec la fonction successeur. donc au lieu im en utilisant (+) comme la fonction pour ma base plier

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 

premières n valeurs, fait 'manuellement':

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 

Ma tentative de définitions formelles thru approche ci-dessus:

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) 

Autre tentative avec un tableau récurrent récursif (pas différent de manière significative):

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. 

Mes questions sont ...

1. Toutes les suggestions générales, différentes appraoches à t-il la fonction? Je ne peux pas sembler trouver un moyen d'éviter les débordements sauf pour utiliser un style très «impératif» qui n'est pas mon intention lorsque j'utilise haskell et j'essaye de coder dans un style idiomatique
2. Comment mon problème hors-un peut être traité donc je peux commencer 'proprement' tout en bas avec succ
3. Strictité et gauches contre les plis droits. Y a-t-il un moyen de travailler dans seq? D'une certaine manière que je peux utiliser foldl1' au lieu de foldr1 et éviter le problème décrit ci-dessus?

Answer 1

1. Voir point 3. Bien que cela fonctionne pour définir ces opérations de cette façon, et vous pouvez le faire sans trop-pleins, il est une approche extrêmement inefficace. Votre temps d'exécution est linéaire dans la réponse, car vous finissez par faire des ajouts répétés.

2. La raison pour laquelle vous obtenez le off-by-one est essentiellement parce que vous utilisez foldr1 f au lieu de foldr f avec une identité.

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

   avis il y a une demande moins + dans le cas de foldr1. Pourquoi ne pas simplement changer l'ordre des arguments en (^)? De cette façon, vous pouvez utiliser un pli gauche:

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

   Maintenant, vous pouvez utiliser la version stricte, foldl1'. Il ne déborde plus, mais il est bien sûr extrêmement inefficace.