ghc/tests/lib/should_run/memo002.hs

   1 module Main where
   2
   3 import Memo     ( memo )
   4 import List     ( genericLength, genericReplicate )
   5 import System   ( getArgs )
   6
   7 main :: IO ()
   8 main = do (arg:_) <- getArgs
   9           mapM_ printTriple [ (i,fib i,mfib i) | i <- [10..read arg] ]
  10   where printTriple (i,fi,mfi) = do print i
  11                                     print fi
  12                                     print mfi
  13                                     putStrLn ""
  14
  15 -- There is not much point in memoising Integers, so we use unary "numbers" instead
  16 mfib :: Integer -> Integer
  17 mfib = genericLength . mfib' . flip genericReplicate ()
  18
  19 mfib' :: [()] -> [()]
  20 mfib' = memo ufib
  21
  22 ufib :: [()] -> [()]
  23 ufib []              = [()]
  24 ufib [()]            = [()]
  25 ufib (():n1@(():n2)) = mfib' n1 ++ mfib' n2
  26
  27 fib :: Integer -> Integer
  28 fib 0 = 1
  29 fib 1 = 1
  30 fib n = fib (n-1) + fib (n-2)