Ackermann.hs

import Data.List (foldl')

update :: (Int, [Int]) -> (Int, [Int])
update (n, [])   = (n, [])
update (n, 0:ms) = (n+1, ms)
-- optimization: ack(1, n) = n + 2
update (n, 1:ms) = (n+2, ms)
update (0, m:ms) = (1, (m-1):ms)
update (n, m:ms) = (n-1, m:(m-1):ms)

display :: (Int, [Int]) -> String
display (n, ms) = foldl' (\s m -> show m ++ ' ' : s) (show n) ms

limit :: Eq a => [a] -> [a]
limit [] = []
limit [a] = [a]
limit (a1:a2:as)
    | a1 == a2  = [a1]
    | otherwise = a1 : limit (a2 : as)

main :: IO ()
main = mapM_ (putStrLn . display) $ limit $ iterate update (5, [3])