Timing subsequencesOfSize

gistfile1.hs

import System.TimeIt
import System.Environment
import Text.Printf

subsequencesOfSize1 :: Int -> [a] -> [[a]]
subsequencesOfSize1 n xs = let l = length xs
                          in if n>l then [] else subsequencesBySize xs !! (l-n)
 where
   subsequencesBySize [] = [[[]]]
   subsequencesBySize (x:xs) = let next = subsequencesBySize xs
                               in zipWith (++) ([]:next) (map (map (x:)) next ++ [[]])

-- this one is faster
subsequencesOfSize2 :: Int -> [a] -> [[a]]
subsequencesOfSize2 n xs | n > length xs = []
subsequencesOfSize2 n xs = subsequencesBySize xs !! n where
  subsequencesBySize    []  = [[[]]]
  subsequencesBySize (x:xs) = zipWith (++) ([] : map (map (x:)) next) (next ++ [[]])
    where next = subsequencesBySize xs

-- e.g. k = 3, n = 150
main = do
  (ks:ns:_) <- getArgs
  let k = read ks
      n = read ns :: Int
      time e = timeItT $ seq e (return e)
  print ("k, n:", k, n)
  (t2,r2) <- time $ length $ subsequencesOfSize2 k [1..n]
  putStrLn $ printf "version 2, time: %7.3f, result: %d" t2 r2

  (t1,r1) <- time $ length $ subsequencesOfSize1 k [1..n]
  putStrLn $ printf "version 1, time: %7.3f, result: %d" t1 r1