sorting - 通用排序功能的最通用可能/有意义的签名

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 纯粹是为了方便，所涉及的列表很可能永远不会实际分配。