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)
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
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]) (,[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],) ([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]) (,[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],) ([0,1,2,3,4,5,6],)
And that can just be
++ combined with the
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