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

• This is really clever – Paul Nov 14 at 4:10
• this repeats the old inits bug which makes (last $subOneLists xs !! n) quadratic in n. My version as well as the newer, corrected version of inits in the library makes it linear. – Will Ness Nov 14 at 13:43 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  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.

• makes me wonder that maybe there should be revinits in the library somewhere... – Will Ness Nov 14 at 13:28
• Would probably make more sense to make that a rewrite rule for tails . reverse, if even necessary. – leftaroundabout Nov 14 at 13:44
• I meant reversed_inits [1..] !! 10 == [10,9..1]. :) (i.e. map reverse . inits but linear) – Will Ness Nov 14 at 13:46
• Ok, reverse . tails . reverse... yeah, that's ah bit meh. Still – I don't think it's good to pack base with every combination of reversal and disassembly. If you use any of these, then it's probably not optimal for performance anyway (compared to something Data.Vector based), and if performance isn't that critical then just combine simple list functions. – leftaroundabout Nov 14 at 13:51
• see my updated comment. It's supposed to be linear, that's the point. and work for infinite inputs too. – Will Ness Nov 14 at 13:52