import Control.Monad
import qualified Data.Array as A
import Data.Array.IArray
import Data.Array.ST
import Data.List
import Data.List.Utils




disSort1
  :: (Ord a, Num a, Enum a, Ord b)
  => [b] -> [a] -> [b]
disSort1 xs is =
  let is_ = sort is
      (sub, rest) = partition ((`elem` is_) . fst) $ zip [0 ..] xs
  in map snd . merge rest . zip is_ . sort $ map snd sub



disSort2
  :: (Ord a)
  => [a] -> [Int] -> [a]
disSort2 xs is =
  let as = A.listArray (0, length xs - 1) xs
      sub = zip (sort is) . sort $ map (as !) is
  in elems $ as // sub




disSort3 :: [Int] -> [Int] -> [Int]
disSort3 xs is =
  elems . runSTUArray $
  do as <- newListArray (0, length xs - 1) xs
     sub <- (zip (sort is) . sort) Control.Applicative.<$> mapM (readArray as) is
     mapM_ (uncurry (writeArray as)) sub
     return as

main :: IO ()
main = do
  let xs = [7, 6, 5, 4, 3, 2, 1, 0]
      is = [6, 1, 7]
  print $ disSort1 xs is
  print $ disSort2 xs is
  print $ disSort3 xs is