# 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 -> ([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?

• Welcome to CodeReview, thrau. I hope you get some fine answers! – Legato Apr 23 '15 at 16:57
• Is selections your goal, or is mark also important in its own right? – 200_success Apr 23 '15 at 21:19
• just need the list permutations, mark is not necessary – thrau Apr 23 '15 at 23:31

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