Haskell -- sort list with impure function

haskell, io, sorting

Solution

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

Problem

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.

Original source