Как отсортировать список [MVar a], используя значения?

Question

Как можно отсортировать список [MVar a]? используя в качестве элемента для сравнения в сортировке. Например:

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

Я не могу придумать пути, не нарушая другие темы.

Обновление: Мне нужно отсортировать список, потому что я хочу реализовать подсчет ссылок, такой как MVar, и возвращать всегда тот, который содержит наименьшее количество ссылок. Что-то вроде:

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

И в потоке я хочу увеличить 'Int'.

Обновление: В ответах я заметил, что для правильной подписи требуется ввод-вывод, потому что 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

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 для всего списка.