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

Question

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

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

我想不出不破坏其他线程的方法。

更新: 我需要对列表进行排序，因为我想实现像 MVar 这样的引用计数，并始终返回引用最少的那个。像这样的东西:

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

在线程中我想增加“Int”。

更新: 我注意到答案是正确的签名需要 IO 因为 MVar

Answer 1

首先，你的类型签名是不可能的；读取 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