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],[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')
        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?

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

Found a deceptively simple solution.

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

List comprehensions are great.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.