Given a Haskell list, return all sub-lists obtained by removing one element

I am trying to write a Haskell function which takes a list ls and returns all sub-lists obtained by removing one element from ls. An additional constraint is that the returned list of lists must be in the order of the missing element.

Here is what I have. I know there must be a simpler solution.

subOneLists :: [a] -> [[a]]
subOneLists ls = let  helper :: [a] -> [a] -> [[a]] -> [[a]]
                      helper _ [] ss = ss
                      helper ps (x:xs) ss = helper ps' xs ss'
                        where ps' = ps ++ [x]
                              ss' = ss ++ [ps ++ xs]
                 in helper [] ls []

λ> subOneLists [1, 2, 3, 4]
[[2,3,4],[1,3,4],[1,2,4],[1,2,3]]

Here’s a simpler way to implement it:

subOneLists :: [a] -> [[a]]
subOneLists [] = []
subOneLists (x:xs) = xs : map (x :) (subOneLists xs)

Look out for standard functions that can help you!

Prelude Data.List> let subOneLists ls = zipWith (++) (inits ls) (tail $ tails ls)
Prelude Data.List> subOneLists [1, 2, 3, 4]
[[2,3,4],[1,3,4],[1,2,4],[1,2,3]]

This uses the fact that the inits– and tails-elements at corresponding index always recombine to the original list, but with a variably splitting point:

Prelude Data.List> let ls = [0..7] in mapM_ print (zip (inits ls) (tails ls))
([],[0,1,2,3,4,5,6,7])
([0],[1,2,3,4,5,6,7])
([0,1],[2,3,4,5,6,7])
([0,1,2],[3,4,5,6,7])
([0,1,2,3],[4,5,6,7])
([0,1,2,3,4],[5,6,7])
([0,1,2,3,4,5],[6,7])
([0,1,2,3,4,5,6],[7])
([0,1,2,3,4,5,6,7],[])

If you now “shift up” that tails, by dropping its head, you effectively lose the head of each of the contained lists:

Prelude Data.List> let ls = [0..7] in mapM_ print (zip (inits ls) (tail $ tails ls))
([],[1,2,3,4,5,6,7])
([0],[2,3,4,5,6,7])
([0,1],[3,4,5,6,7])
([0,1,2],[4,5,6,7])
([0,1,2,3],[5,6,7])
([0,1,2,3,4],[6,7])
([0,1,2,3,4,5],[7])
([0,1,2,3,4,5,6],[])

And that can just be ++ combined with the inits again.

List as an abstract concept can have many representations.

In particular, with a list being represented by its “zipper” – a pairing of a reversed prefix and a suffix, it becomes possible to have a linear solution to this problem, as opposed to the quadratic one which is unavoidable with the plain linear representation :

picks :: [a] -> [([a], [a])]
picks []     = []
picks (x:xs) = go [x] xs
   where
   go pref suff@(x:xs) = (pref,suff) : go (x:pref) xs
   go pref []          = [(pref,[])]

Using this, your problem becomes

foo = map ((a,b) -> revappend (tail a) b) . picks

revappend a b = foldl (flip (:)) b a

This is of course again quadratic, but maybe you could keep the prefixes reversed, to stay linear:

import Control.Arrow (first)

foo' = map (first tail) . picks               -- or,
 --  = map ((x,y) -> (tail x, y)) . picks