{-# LANGUAGE CPP #-} module IntMemo(memoInt) where import Prelude hiding (lookup) import CmdLineEnv(argFlag) #ifndef __NHC__ #define STRICTARG(x) (x){-#STRICT#-} #else #define STRICTARG(x) (x) #endif data IntMemo a = Tip | Node a (IntMemo a) (IntMemo a) lookup :: Int -> IntMemo a -> Maybe a lookup :: Int -> IntMemo a -> Maybe a lookup Int n IntMemo a m = case IntMemo a m of IntMemo a Tip -> Maybe a forall a. Maybe a Nothing Node a x IntMemo a l IntMemo a r -> case Int n of Int 0 -> a -> Maybe a forall a. a -> Maybe a Just a x Int _ -> Int -> IntMemo a -> Maybe a forall a. Int -> IntMemo a -> Maybe a lookup (Int n Int -> Int -> Int forall a. Integral a => a -> a -> a `div` Int 2) (STRICTARG(if n `mod` 2==0 then l else r)) memoInt :: (Int->a)->(Int->a) memoInt :: (Int -> a) -> Int -> a memoInt Int -> a f = if Bool memoOn then Int -> a g else Int -> a f where g :: Int -> a g Int n = if Int nInt -> Int -> Bool forall a. Ord a => a -> a -> Bool <Int 0 then case Int -> IntMemo a -> Maybe a forall a. Int -> IntMemo a -> Maybe a lookup (-Int n) IntMemo a negtable of Just a x -> a x else case Int -> IntMemo a -> Maybe a forall a. Int -> IntMemo a -> Maybe a lookup Int n IntMemo a table of Just a x -> a x table :: IntMemo a table = Int -> Int -> IntMemo a tabulate Int 0 Int 1 negtable :: IntMemo a negtable = Int -> Int -> IntMemo a tabulate Int 0 (-Int 1) tabulate :: Int -> Int -> IntMemo a tabulate Int n Int b = a -> IntMemo a -> IntMemo a -> IntMemo a forall a. a -> IntMemo a -> IntMemo a -> IntMemo a Node (Int -> a f Int n) (Int -> Int -> IntMemo a tabulate Int n (STRICTARG(2*b))) (Int -> Int -> IntMemo a tabulate (STRICTARG(n+b)) (STRICTARG(2*b))) memoOn :: Bool memoOn = [Char] -> Bool -> Bool argFlag [Char] "memoint" Bool True