Haskell - список сортировки с нечистой функцией

Как я могу сортировать список с функцией сравнения IO?

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

Sortby ожидает (a->a->Ordering), и я не знаю, как с этим бороться. Я слишком ленив, чтобы реализовать быструю сортировку.

Ответы

Ответ 1

Я боюсь, что нет простого способа. Если бы можно было поднять

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

к

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

вы можете увидеть порядок сравнений в реализации sortBy, нарушив ссылочную прозрачность.

В общем, легко перейти от xxxM в xxx, но не обратно.

Возможные варианты:

  • Реализация метода монодальной сортировки
  • Используйте библиотеку monadlist, которая содержит сортировку вставки (как в ответе dflemstr)
  • Используйте unsafePerformIO как хак

  • Переключитесь на сортировку по ключу и используйте преобразование Шварца

    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

Ответ 2

Функция sortBy использует сортировку слияния как алгоритм в GHC, но в отчете Haskell 98 указано, что нужно использовать сортировку вставки.

Для простоты, потому что у меня нет компилятора, поэтому я не могу проверить свой код, я буду реализовывать сортировку вставки здесь:

import Data.Foldable (foldrM)

insertByM :: (a -> a -> IO Ordering) -> a -> [a] -> IO [a]
insertByM _   x [] = return [x]
insertByM cmp x [email protected](y:ys') = do
  p <- cmp x y
  case p of
    GT -> do
      rest <- insertByM cmp x ys'
      return $ y : rest
    _ -> return $ x : ys

sortByM :: (a -> a -> IO Ordering) -> [a] -> IO [a]
sortByM cmp = foldrM (insertByM cmp) []

Как я уже сказал, я не тестировал этот код, но он мог/должен работать.

Ответ 3

О, я сделал это раньше! Объединить сортировку с монадическим компаратором:

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

Из моего сообщения в блоге: http://unknownparallel.wordpress.com/2012/07/03/using-monadic-effects-to-reverse-a-merge-sort/

Ответ 4

Был ли Ларри Уолл, что Лень - одна из трех великих достоинств программиста?

Кажется, вы хотите преобразовать функцию типа (a → a → b) в функцию типа (a → a → c b). Включите это в Hoogle. Теперь, если вы знаете, что IO - Монада, вы увидите о 10-м матче в liftM2. Проверьте тип (liftM2 sortBy), что вы хотите?