通用排序函数的最通用可能/有意义的签名

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