Skip to content

Instantly share code, notes, and snippets.

@23Skidoo
Created Apr 20, 2013
Embed
What would you like to do?
Loop-unrolled Ackermann function.
-- See http://stackoverflow.com/q/16115815/242169
-- Run with +RTS -kc1M to avoid space leak
--
-- Test:
-- $ time ./Test +RTS -kc1M
-- 65533
-- ./Test +RTS -kc1M 6,30s user 0,04s system 97% cpu 6,516 total
---
{-# LANGUAGE CPP #-}
module Main where
data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !Int
ack0 :: Int -> Int
ack0 n =(n+1)
#define C(a) a
#define CONCAT(a,b) C(a)C(b)
#define AckType(M) CONCAT(ack,M) :: Int -> Int
AckType(1)
AckType(2)
AckType(3)
AckType(4)
#define AckDecl(M,M1) \
CONCAT(ack,M) n = case n of { 0 -> CONCAT(ack,M1) 1 \
; 1 -> CONCAT(ack,M1) (CONCAT(ack,M1) 1) \
; _ -> CONCAT(ack,M1) (CONCAT(ack,M) (n-1)) }
AckDecl(1,0)
AckDecl(2,1)
AckDecl(3,2)
AckDecl(4,3)
ack :: P -> (Int -> Int) -> Int
ack (P m n) k = case m of
0 -> k (ack0 n)
1 -> k (ack1 n)
2 -> k (ack2 n)
3 -> k (ack3 n)
4 -> k (ack4 n)
_ -> case n of
0 -> ack (P (m-1) 1) k
1 -> ack (P (m-1) 1) (\a -> ack (P (m-1) a) k)
_ -> ack (P m (n-1)) (\a -> ack (P (m-1) a) k)
main :: IO ()
main = print $ ack (P 4 1) id
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment