Cfrtjryk

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, with

foo' = map (first tail) . 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.