我已经做了很多工作来提出一些提示/示例,但到目前为止没有任何结果。

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

也许我应该只问有关Traversable t => t a排序的问题?

最佳答案

您当然可以对任意Traversable进行排序,方法是将其折叠以生成列表,向量或堆,然后使用mapAccumLmapAccumR将所有元素放回去。问题在于,这可能不如直接分类容器那样有效。

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

请注意,toListfromList的使用纯粹是为了方便起见,而且涉及的列表很可能从未真正分配。

10-06 12:49