module Main where main :: IO () main = do -- recurrence relations -- A(n) = A(n-2) + 2B(n-1) -- B(n) = A(n-1) + B(n-2) -- A(0) = 1, A(1) = 0 -- B(0) = 0, B(1) = 1 let boardWidths = [ x | x <- [1..30], x `mod` 2 == 0] mapM_ (putStrLn . format faster_an) boardWidths
putStrLn . format faster_an $ 100 format :: (Int -> Int) -> Int -> String format f x = show x ++ " => " ++ show (f x) -- Implementation of the recurrence relations without direct recursion. an :: (Int -> Int) -> (Int -> Int) -> Int -> Int an an' bn' n | n == 0 = 1 | n == 1 = 0 | otherwise = an' (n - 2) + 2 * bn' (n - 1) bn :: (Int -> Int) -> (Int -> Int) -> Int -> Int bn an' bn' n | n == 0 = 0 | n == 1 = 1 | otherwise = an' (n - 1) + bn' (n - 2) -- Memoization by lazy evaluation an_list :: [Int] an_list = fmap (an faster_an faster_bn) [0..] bn_list :: [Int] bn_list = fmap (bn faster_an faster_bn) [0..] faster_an :: Int -> Int faster_an n = an_list !! n faster_bn :: Int -> Int faster_bn n = bn_list !! n