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]]
up vote 13 down vote accepted

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
  • 3
    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
  • 1
    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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.