haskell - гипероперационная (акерманнская) функция, тетрация

Question

Я пытаюсь написать гипероперационную функцию в haskell.

Обычно она записывается как ackermann(a,b,n), но для частичного применения я думаю, что имеет смысл ставить n на первое место.Таким образом, я называю это hypOp n a 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)))
   foldr1 (+) [a, a, a]  = a + (a + a)
   

   Обратите внимание, что в случае foldr1.

3. Как насчет простого изменения порядка аргументов на (^)? Таким образом, вы можете использовать левую складку:

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

   Теперь вы можете использовать строгую версию, foldl1'. Он больше не переполняется, но, конечно, крайне неэффективен.