[longlivedeath]

Thank you, now I see. Here's my version:

    shuffle :: (ChoiceMonad m, Eq a) => [a] -> m [a]
    shuffle [] = return []
    shuffle elems = do 
      x <- choice elems
      xs <- shuffle (x `delete` elems)
      return (x:xs)