Haskell - 具有不纯函数的排序列表

Question

如何使用IO比较功能对列表进行排序？

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

Sortby期待(a->a->Ordering),我不知道,如何处理它.我懒得自己快速排序.

Answer 1

我担心没有简单的方法.如果有可能举起

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

至

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

您可以看到执行中的比较顺序sortBy,违反参照透明度.

一般来说,这很容易xxxM,xxx但不是相反.

可能的选择:

• 实现monadic排序方法
• 使用单子库,其中包含插入排序(如dflemstr的答案)
• 使用unsafePerformIO一劈

• 切换到按键排序并使用Schwartzian变换

  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