Я пытаюсь написать функцию гипероперации в haskell.
Обычно это записывается как ackermann (a, b, n)
, но для целей частичного применения, я думаю, имеет смысл сначала поставить n
. Поэтому я называю это hypOp nab
Форма, которую я нашел наиболее естественной, использует свертки реплицировать
списки следующим образом:
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.
Итак, мои вопросы ...
succ
seq
? Каким-то образом я могу использовать foldl1 '
вместо foldr1
и избежать проблемы, описанной выше?