uniqueBSTs.hs

import Text.Printf
import Control.Exception
import System.CPUTime
 
time :: IO t -> IO t
time a = do
    start <- getCPUTime
    v <- a
    end   <- getCPUTime
    let diff = (fromIntegral (end - start)) / (10^12)
    printf "Computation time: %0.3f sec\n" (diff :: Double)
    return v

main = do
    putStrLn "Starting..."
    time $ memoized_countUniqueBSTs 5 `seq` return ()
    putStrLn "Done."

memoized_countUniqueBSTs :: Int -> Integer
memoized_countUniqueBSTs n = (map countUniqueBSTs [0..]) !! n
    where   countUniqueBSTs 0 = 1
            countUniqueBSTs 1 = 1
            countUniqueBSTs n = sum $ zipWith (*) (computedBSTs n) (reverse $ computedBSTs n)
            computedBSTs n = map memoized_countUniqueBSTs [0..(n-1)]
            
-- countUniqueBSTs :: Int -> Int
-- countUniqueBSTs 0 = 1
-- countUniqueBSTs 1 = 1
-- countUniqueBSTs n = sum $ zipWith (*) computedBSTS (reverse computedBSTS)
--     where computedBSTS = map countUniqueBSTS [0..(n-1)]