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

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