Haskell marking procedure for non-unique lists I'm writing a function for generating solutions for a backtracking search problem. To that end, I need to mark an item from a list by removing it from that list, and placing it in a second list.

So I have a pair of lists:


non-marked items
marked items


and my method generates all distinct list pairs of possible markings. Because the list may contain duplicates, I'm selecting the marked item via the index.

Example:

mark 0 ([1,2,2],[]) == ([2,2],[1])
selections ([1,2,2],[]) == [([2,2],[1]),([1,2],[2])]


Code so far:

mark :: Int -&gt; ([a], [a]) -&gt; ([a], [a])
mark i (src,tgt) = (src',tgt')
    where
        src' = let (ys,zs) = splitAt i src in ys ++ (tail zs)
        tgt' = tgt ++ [e]
        e = src !! i

selections :: Eq a =&gt; ([a],[a]) -&gt; [([a],[a])]
selections pair@(left,_) = nub [ mark i pair | i &lt;- [0..((length left)-1)] ]


I'm not happy with the implementation: it seems crude, looks ugly, and I think it's obvious that someone with a background in imperative languages wrote this function.

Can this be solved more elegantly, with Array or other list mechanisms, e.g. a fold?
Found a deceptively simple solution.

selections (left,right) = nub [(delete o left,right ++ [o]) | o &lt;- left]


List comprehensions are great.