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.
mark 0 ([1,2,2],) == ([2,2],) selections ([1,2,2],) == [([2,2],),([1,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?