Haskell -- sort list with impure function

Question

How can I sort list with IO Compare function?

sortWith :: [String] -> (String -> String -> IO Ordering) -> IO [String]

Sortby expects (a->a->Ordering) and I don't know, how to deal with it. I am too lazy to implement quick sort myself.

Answer 1

Oh, I've done this one before! Merge sort with monadic comparator:

type MComparator m a = a -> a -> m Ordering

sortByM :: (Monad m, Functor m) => MComparator m a -> [a] -> m [a]
sortByM cmp []  = return []
sortByM cmp [x] = return [x]
sortByM cmp xs = do
  let (ys, zs) = partition xs
  ys' <- sortByM cmp ys
  zs' <- sortByM cmp zs
  merge ys' zs'
  where merge [] bs = return bs
        merge as [] = return as
        merge (a:as) (b:bs) = do
          comparison <- cmp a b
          case comparison of
            LT -> (a:) <$> merge as (b:bs)
            _  -> (b:) <$> merge (a:as) bs
        partition xs = splitAt (length xs `quot` 2) xs

From my blog post: http://unknownparallel.wordpress.com/2012/07/03/using-monadic-effects-to-reverse-a-merge-sort/

Answer 2

I'm afraid there is no simple way. If it was possible to lift

sortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a]

to

sortByM :: (Ord a, Monad m) => (a -> a -> m Ordering) -> [a] -> m [a]

you could see the order of comparisons in implementation of sortBy, violating referential transparency.

In general, it's easy to go from xxxM to xxx but not conversely.

Possible options:

• Implement a monadic sorting method
• Use the monadlist library, which contains insertion sort (as in dflemstr's answer)
• Use unsafePerformIO as a hack

• Switch to sorting by key and use the Schwartzian transform

  sortOnM :: (Monad m, Ord k) => (a -> m k) -> [a] -> m [a]
  sortOnM f xs = liftM (map fst . sortBy (comparing snd)) $
                   mapM (\x -> liftM (x,) (f x)) xs