Generalizing a combinatoric function?

Question

I've been solving a few combinatoric problems on Haskell, so I wrote down those 2 functions:

permutations :: (Eq a) => [a] -> [[a]]
permutations [] = [[]]
permutations list = do
    x  <- list
    xs <- permutations (filter (/= x) list)
    return (x : xs)

combinations :: (Eq a, Ord a) => Int -> [a] -> [[a]]
combinations 0 _ = [[]]
combinations n list = do
    x  <- list
    xs <- combinations (n-1) (filter (> x) list)
    return (x : xs)

Which works as follows:

*Main> permutations [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
*Main> combinations 2 [1,2,3,4]
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Those were uncomfortably similar, so I had to abstract it. I wrote the following abstraction:

combinatoric next [] = [[]]
combinatoric next list = do
    x  <- list
    xs <- combinatoric next (next x list)
    return (x : xs)

Which receives a function that controls how to filter the elements of the list. It can be used to easily define permutations:

permutations :: (Eq a) => [a] -> [[a]]
permutations = combinatoric (\ x ls -> filter (/= x) ls)

But I couldn't define combinations this way since it carries an state (n). I could extend the combinatoric with an additional state argument, but that'd become too clunky and I remember such approach was not necessary in a somewhat similar situation. Thus, I wonder: is it possible to define combinations using combinatorics? If not, what is a better abstraction of combinatorics which successfully subsumes both functions?

Answer 1

This isn't a direct answer to your question (sorry), but I don't think your code is correct. The Eq and Ord constraints tipped me off - they shouldn't be necessary - so I wrote a couple of QuickCheck properties.

prop_numberOfPermutations xs = length (permutations xs) === factorial (length xs)
    where _ = (xs :: [Int])  -- force xs to be instantiated to [Int]

prop_numberOfCombinations (Positive n) (NonEmpty xs) = n <= length xs ==>
        length (combinations n xs) === choose (length xs) n
    where _ = (xs :: [Int])


factorial :: Int -> Int
factorial x = foldr (*) 1 [1..x]

choose :: Int -> Int -> Int
choose n 0 = 1
choose 0 r = 0
choose n r = choose (n-1) (r-1) * n `div` r

The first property checks that the number of permutations of a list of length n is n!. The second checks that the number of r-combinations of a list of length n is C(n, r). Both of these properties fail when I run them against your definitions:

ghci> quickCheck prop_numberOfPermutations
*** Failed! Falsifiable (after 5 tests and 4 shrinks):    
[0,0,0]
3 /= 6
ghci> quickCheck prop_numberOfCombinations 
*** Failed! Falsifiable (after 4 tests and 1 shrink):     
Positive {getPositive = 2}
NonEmpty {getNonEmpty = [3,3]}
0 /= 1

It looks like your functions fail when the input list contains duplicate elements. Writing an abstraction for an incorrect implementation isn't a good idea - don't try and run before you can walk! You might find it helpful to read the source code for the standard library's definition of permutations, which does not have an Eq constraint.