random order

What is an efficient way to randomize the order of something, for example characters in a string or places in an array, without repeating anything before you ran trough all characters/arrayplaces?

>>8
With the right type signature, >>6 is actually O(n) if use it on a DiffArray.

import Monad
import Random
import Data.Array.IArray

randomize :: (IArray a e, Enum i, Random i, Ix i) => a i e -> IO (a i e)
randomize array =
   foldM step array $ reverse [lo..hi]
   where step a i = fmap (swap a i) $ randomRIO (lo, i)
         swap a i j = a // [(j, a!i), (i, a!j)]
         (lo, hi) = bounds array