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

Posted on

Problem

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]]
``````

Solution

Here’s a simpler way to implement it:

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

``````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])
(,[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],)
([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])
(,[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],)
([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,[])]
``````

``````foo = map ((a,b) -> revappend (tail a) b) . picks
``````import Control.Arrow (first)