Why doesn't this list comprehension in haskell include lists of size < n

Question

I am looking at this code for generating combinations in Haskell

combinations :: Int -> [a] -> [[a]]
combinations 0 _ = [[]]
combinations n xs = [ xs !! i : x | i <- [0..(length xs)-1] 
                                  , x <- combinations (n-1) (drop (i+1) xs) ]

I tried to visualize how the tree gets expanded, but I do not understand why the list doesn't include the paths in red.

combinations 3 "abcd"
["abc","abd","acd","bcd"]

All I can see is xs !! i : x ie append the i'th element to the n -1 combinations of it's tail, but why doesn't [d] : [[]] = [d] get included.

Answer 1

What you're trying to do is this: “isolate” each element in the list from the rest, then recurse over the rest. You attempt to achieve this seperation by, on one side, selecting each element with !!, and on the other removing it. But that's not quite what drop does, it's rather a task for deleteBy. That is awkward to use with indices, though:

combinations n xs = [ xs !! i : x | i <- [0..(length xs)-1] 
                                  , x <- combinations (n-1) (xs' i) ]
 where xs' i = snd <$> deleteBy ((==i).fst) (zip [0..] xs)

In general it's rather unidiomatic to index into Haskell lists. A much better approach is to implement this isolation-thing by direct recursion:

foci :: [a] -> [(a,[a])]
foci [] = []
foci (x:xs) = (x,xs) : map (second (x:)) (foci xs)

And then you can do

combinations n xs = [ x₀ : xs'' | (x₀,xs') <- foci xs
                                , xs'' <- combinations (n-1) xs' ]

Answer 2

drop (i+1) xs does not remove the i+1th element, but all the elements with index < i+1.