sorting - Haskell——使用不纯函数对列表进行排序

Question

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

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 很容易，但反之则不然。

可能的选项:

• 实现一元排序方法
• 使用monadlist库，其中包含插入排序(如 dflemstr 的答案)
• 使用unsafePerformIO作为黑客

• 切换到按键排序并使用 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