The following Haskell function computes all the subsets of a set. subsets :: [a] -> [[a]] subsets [] = [[]] subsets (x:xs) = [zs | ys <- subsets xs, zs <- [ys, (x:ys)]] Example of use: *Main> subsets [1,2,3] [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

With the help of the function subsets, one can also compute the subsets of a set of n elements such that each subset has exactly k elements, using the following definition: ksubsets k xs = [ys | ys<-subsets xs, length ys==k] Example of use: *Main> ksubsets 3 [1,2,3,4,5] [[1,2,3],[1,2,4],[1,3,4],[2,3,4],[1,2,5],[1,3,5],[2,3,5],[1,4,5],[2,4,5],[3,4,5]]

*******

Write an efficient variant of ksubsets, that generates all the subsets of a set with n elements having exactly k elements, without generating all such subsets and then computing their length. 

*Main> length (fast_ksubsets 3 [1..100])

161700 that should return a result in less than 10 seconds. *****Hint: assuming you know how to build subsets of k-1 elements, think how you can extend that with one more element that you might or might not need to add to all of them.