11

IO Compare 関数でリストをソートするにはどうすればよいですか?

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ハックとして使う

  • キーによる並べ替えに切り替えて、シュワルツ変換を使用する

    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

あ、これやった事ある！モナドコンパレータを使用したマージソート:

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/

于 2012-07-13T21:57:24.743 に答える
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

怠惰はプログラマーの 3 つの美徳の 1 つだと言ったのはラリー ウォールでしたか?

タイプ (a -> a -> b) の関数をタイプ (a -> a -> cb) の関数に変換したいようです。それをHoogleにプラグインしましょう。ここで、IO がモナドであることがわかっている場合は、liftM2 で 10 番目のマッチ ダウンについて確認できます。(liftM2 sortBy) のタイプを確認してください。それでよろしいですか?

于 2012-07-13T12:01:05.473 に答える