Dfyjkt

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)

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.