Вот как это сделать в общем случае.
Во-первых, вам нужен изменяемый вектор.Вы можете построить это постепенно, когда вы сканируете файл;выделите вектор, который будет настолько большим, насколько вам нужно, и увеличьте размер и скопируйте, когда у вас закончится свободное местоИли вы можете прочитать весь файл, сосчитать разделители записей и выделить необходимое количество места сразу.Это проще, но, вероятно, не приемлемо в реальной жизни.(Стратегия расширения по мере необходимости довольно распространена; если вы когда-либо используете язык, такой как Perl, и переносите строки, прочитанные из файла, в конец массива, это то, что происходит. Perl выделяет некоторое пространство для массива, когда вызаполните его, это увеличивает количество места, выделяет новое пространство и копирует.)
В любом случае, мне лень это делать, поэтому я просто собираюсь создать вектор с некоторыми случайными числами в нем.
Для этого нам понадобится несколько библиотек:
import Control.Monad
import System.Random
import qualified Data.Vector as IV
import qualified Data.Vector.Mutable as MV
import qualified Data.Vector.Generic as V
import qualified Data.Vector.Algorithms.Intro as VA
Нам это не нужно сразу, но в конечном итоге оно нам понадобится, поэтому я подумал, что получуэто не так.
В любом случае, наш изменяемый вектор будет «нормальным» изменяемым вектором, здесь MV.MVector.
Идея изменяемого вектора состоит в том, что вы создаете егои измените его в несколько шагов.В Haskell есть несколько способов сделать этот код чистым для вызывающего кода;Один из них - сделать все внутри монады ST.Ваше действие ST создает вектор, модифицирует его и «замораживает» его в неизменный вектор.Внутри вы используете быстрые операции «изменить это местоположение в куче времени», но внешне у вас есть что-то чистое.(Прочтите статью о ST, если вам нужен аргумент о том, почему это безопасно.)
Еще один способ справиться с изменчивыми данными - просто сделать это внутри монады Все, эм, IO,Это то, что мы собираемся сделать здесь, так как это наиболее удобно.
(Data.Vector.Mutable имеет два предопределенных типа вектора для вас, IOVector и STVector. Мы используем IOVector, которыйпомещает все векторные операции в IO.)
Итак, как и 8 параграфов назад, мы собирались создать изменяемый вектор для сортировки.И вот мы:
randVector :: IO (MV.IOVector Int)
randVector = do
v <- MV.new 10
forM [0..9] $ \x -> do
r <- randomIO :: IO Int
MV.write v x r
return v
Это действие ввода-вывода, которое возвращает новый изменяемый вектор с 10 случайными числами внутри.(Генерация случайных чисел также может быть удобно перенесена в монаду ввода-вывода, поэтому мы сделали это тоже для удобства! Это похоже на то, что мы пишем C, но с более приятным синтаксисом и большей безопасностью типов.)
Это на самом делесложная часть.Для сортировки я импортировал Data.Vector.Algorithms.Intro, который по сути является быстрой сортировкой на месте.Функция с именем sort выполняет фактическую сортировку (в какой бы монаде не был изменяемый вектор).
Действие, которое создает случайный изменяемый вектор и сортирует его по месту, выглядит следующим образом:
sort = VA.sort =<< randVector
Теперь, чтобы распечатать это, все, что нам нужно сделать, это «заморозить» вектор в неизменяемом векторе и распечатать .toList.Или вы можете просто перебрать каждый элемент и распечатать его.
Вот что я придумал в качестве примера:
main = do
v <- randVector
VA.sort v
iv <- V.unsafeFreeze v :: IO (IV.Vector Int)
print . V.toList $ iv
V.unsafeFreeze от Data.Vector.Generic (как вы взаимодействуете свсе векторные типы с одинаковым API), как и V.toList.
В любом случае, стоит отметить, что IO здесь исключительно для удобства.Поскольку вы строите вектор из данных файла, это уместно.99% времени, однако, вы должны использовать ST.В своем действии ST создайте вектор, отсортируйте его, заморозьте его и верните замороженную версию.
Аналогичный пример с использованием STVector:
randVector :: ST s (Vector Int)
randVector = do
vec <- new 10
rand <- newSTRef 17
forM_ [0..9] $ \index -> do
randN <- readSTRef rand
let randN' = (fst . next . mkStdGen) randN
writeSTRef rand randN'
write vec index randN'
unsafeFreeze vec
Затем выполните с:
*Main> runST randVector
fromList [679560,1422110406,306332632,1905242129,692062628,393451229,355476175,1240028023,873588529,1181443777] :: Data.Vector.Vector