泛型排序函数的最泛型可能/有意义的签名

Question

我已经做了相当多的谷歌来获得一些提示/例子，到目前为止没有任何用处。

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

也许我应该只是问排序一个Traversable t => t a ?

Answer 1

您当然可以对任意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的使用纯粹是为了方便，所涉及的列表很可能永远不会被实际分配。

Answer 2

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