Haskell powerset sublists with fixed length

Question

It's well known that the powerset of a list: {1,2,3,4} is {{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3},{4},{1,4},{2,4},{1,2,4},{3,4},{1,3,4},{2,3,4},{1,2,3,4}}

the haskell code I got for that problem is:

potencia [] = [[]]

potencia (a:bs) = potencia bs ++ map (a:) (potencia bs)

Now, how would I get a list of sublists of the same length?, for example, the list above would generate the next list of sublists of length 3 = {{1,2,3},{1,2,4},{1,3,4}}

I'm a student sorry for my english, thanks in advance... XD

Answer 1

How about

sublists  _     0 = [[]]
sublists  []    _ = []
sublists (x:xs) n = sublists xs n ++ map (x:) (sublists xs $ n - 1)

Which is very similar to the code you had but just has two decreasing parameters, the length and the list.

Also, for more advanced Haskellers

powerset = flip runCont id . foldM step [[]]
  where step xs x = cont $ \c -> c xs ++ c (map (x:) xs)

is a powerset implementation without recursion using continuations. Doing the same with the sublists function is an interesting challenge.

Answer 2

I'm thinking just

subsequencesOf :: Int -> [a] -> [[a]]
subsequencesOf n = filter ((== n) . length) . subsequences

Which will give you

> subsequencesOf 3 [1, 2, 3, 4]
[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

Although I find it weird that this isn't an operation in Data.Set, and that Set isn't a monad (and therefore has its own version of replicateM.) I guess there might be obstacles in the way there.