如何使用值对列表[MVar a]进行排序？

Question

如何对[MVar a]列表进行排序？使用a作为要在排序中进行比较的元素.例如:

sortList :: [MVar Int] -> [MVar Int]

我不能在没有打破其他线程的情况下想办法.

更新: 我需要对列表进行排序,因为我想实现像MVar这样的引用计数,并始终返回具有最少引用的引用计数.就像是:

getLeastUsed :: [MVar Int] -> MVar Int
getLeastUsed = head . sortList

在线程中我想增加'Int'.

更新: 由于答案,我认为rigth签名需要IO,因为MVar

Answer 1

首先,你的类型签名是不可能的; 阅读a MVar并不是指称透明的(希望显而易见的是 - 这就是他们的目的!).这有两个后果:

• 您的排序功能必须返回一个IO动作
• 列表将根据每个MVar读取时看到的值进行排序; 它不仅可能在您使用列表时无效,它可能会在您读取最后一个值之前中途改变,以使第一个值过期.

前者是不可避免的,假设后者对于你的目的是可以接受的,你可以基本上做@hammar演示的内容.

但是,鉴于排序很快就会过时,并且你似乎对最小元素感兴趣,你可能会发现这样的东西更直接有用,因为除了排序之外几乎没用:

import Control.Applicative
import Data.List
import Data.Ord

leastUsed :: [MVar Int] -> IO (MVar Int)
leastUsed vars = fst . minimumBy (comparing snd) . zip vars <$> mapM readMVar vars

Answer 2

最简单的方法可能是做一个decorate-sort-undecorate,你首先读出MVars的所有当前值,然后使用它们作为键进行排序.

import Data.List (sortBy)
import Data.Ord (comparing)

sortList :: [MVar Int] -> IO [MVar Int]
sortList vars = do
    currentValues <- mapM readMVar vars
    return . map snd . sortBy (comparing fst) $ zip currentValues vars

请注意,结果列表可能未完全排序,因为MVars的值自读取后可能已更改.但是,如果您关心这一点,您可能应该使用单个MVar作为整个列表.