Haskell marking procedure for non-unique lists

Question

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 -> ([a], [a]) -> ([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 => ([a],[a]) -> [([a],[a])]
selections pair@(left,_) = nub [ mark i pair | i <- [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?

Answer 1

Found a deceptively simple solution.

selections (left,right) = nub [(delete o left,right ++ [o]) | o <- left]

List comprehensions are great.