11

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

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

Sortby 期望(a->a->Ordering)但我不知道如何处理它。我懒得自己实现快速排序。

4

4 回答 4

16

恐怕没有简单的方法。如果可以举起

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 变换

    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
于 2012-07-13T12:29:32.963 回答
3

该sortBy函数使用归并排序作为 GHC 中的算法，但 Haskell 98 报告规定应该使用插入排序。

为简单起见，因为我没有编译器，所以我无法测试我的代码，我将在这里实现插入排序：

import Data.Foldable (foldrM)

insertByM :: (a -> a -> IO Ordering) -> a -> [a] -> IO [a]
insertByM _   x [] = return [x]
insertByM cmp x ys@(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) []

正如我所说，我没有测试过这段代码，但它可以/应该工作。

于 2012-07-13T12:09:17.413 回答
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

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

于 2012-07-13T21:57:24.743 回答
-3

是拉里·沃尔（Larry Wall）说的，懒惰是程序员的三大美德之一吗？

您似乎想将 (a -> a -> b) 类型的函数转换为 (a -> a -> cb) 类型的函数。让我们将其插入Hoogle。现在，如果您知道 IO 是 Monad，您将在 liftM2 中看到第 10 场比赛。检查（liftM2 sortBy）的类型，是你想要的吗？

于 2012-07-13T12:01:05.473 回答