通用排序函数的最通用 possible/meaningful 签名

Question

我已经进行了大量的谷歌搜索以得出一些 hints/examples，但到目前为止无济于事。

是否有比基于列表的排序算法更通用的方法来实现排序算法？我可以直接使用 sortGeneric :: IsList l => l a -> l a 但这似乎是个坏主意，因为 IsList 只不过是对 OverloadedLists.

的支持

也许我应该问一下 Traversable t => t a 的排序？

Answer 1

怎么样

sortGeneric :: (Ord a, Traversable t) => t a -> t a

Answer 2

您当然可以对任意 Traversable 进行排序，方法是折叠它以生成列表、向量或堆，然后使用 mapAccumL 或 mapAccumR 将所有元素放回去.麻烦的是，这可能比直接排序容器效率低。

import qualified Data.PQueue.Min as Q
import Data.Foldable (toList)
import Data.Traversable (Traversable (..))
import Data.Tuple (swap)
import Control.Monad.Trans.State.Strict

sort xs = mapAccumL' go (Q.fromList . toList $ xs) xs where
  go h _ = swap $ Q.deleteFindMin h

mapAccumL' :: Traversable t =>
              (a -> b -> (a, c)) -> a -> t b -> t c
mapAccumL' f s t = flip evalState s $
   traverse (\q -> state $ swap . flip f q) t

请注意，使用 toList 和 fromList 纯粹是为了方便，所涉及的列表很可能永远不会实际分配。

通用排序函数的最通用 possible/meaningful 签名

Most generic possible/meaningful signature for a generic sorting function

sorting

haskell

generic-list