Search code examples
haskellfunctional-programming

Remove various elements by position

I am doing an exercise for class which after a while racking my brains I found the theory way to do it but can't figure out the way to do in Haskell.
The exercise being:

Having a list xs with n different elements. The combination of the n elements of the list xs taking them from m to m (with m <= n) are all the possible sets of m elements (with no repetitions) that can be formed from the original n elements.

The order of the elements does not have importance (meaning that "abc" is considered the same combination as "bca").

For example:

comb 0 "abcd" -> [""]
comb 3 "bcd" -> ["bcd"]
comb 2 "bcd" -> ["cd","bd","bc"]
comb 3 "abcd" -> ["bcd", "acd", "abd", "abc"]

Define a function comb that takes a natural number m and a list xs with n different elements.

The only way I could find is that I need a value that will my "position pointer" pp, that way it will remove length xs - m elements after that pointer and then in the recursive call do m + pp, so it "jumps" to the next position. I will write an example in a kind of pseudo-Haskell way:

m = 3   xs = "abcd"   * = pp

*abcd       *remove (length xs - m) after pointer
Solution:  "bcd"  

*Recursively jump pointer by (length xs - m):

"a*bcd"   ->   "acd"
"ab*cd"   ->   "abd"
"abc*d"   ->   "abc"
"abcd*"   ->   [""]

I am really sorry of this kind of invention, I tried to use the pointer analogy because I think it is quite easy to see it that way, and I used I kind of mix of pseudo code and Haskell because do not know how to do it another way.

Solution

  • How to pick n elements from a list?

    comb :: Int -> [a] -> [[a]]

    If n is zero, no matter what the list is, you have a single pick with no elements in it.

    comb 0 _ = [[]]

    Otherwise, if your list is empty, you have no picks at all. (Note how this is different from the above.)

    comb _ [] = []

    Otherwise, your list has a head and a tail. The picks are as follows. First, you have all the picks that include the head, and then all the picks that exclude the head.

    comb n (x:xs) = withHead ++ withoutHead where

    How to build all the picks that exclude the head? That's easy, just apply the function recursively to the tail of the list.

        withoutHead = comb n xs

    What about the picks that include the head? That's also easy, just apply the function recursively to the tail of the list, but this time make the picks one element shorter. Then slap the head in front of each pick.

        withHead = map (x:) (comb (n-1) xs)