Как изменяемые массивы реализованы в Haskell?
Я прочитал много исследовательских работ на эту тему, и они обычно утверждают, что массивы реализованы с использованием монад. Но ни одна из этих работ не дала четкого определения того, как должен быть определен сам массив "type", они дали только определения для функций, использующих монады для доступа или изменения этого типа. Как массивы, имеющие O(1) время для доступа или изменения индексированного элемента, реализованы в Haskell?! (например, STUArray и MArray)
3 ответа
Как массивы, имеющие O(1) время для доступа или изменения индексированного элемента, реализованы в Haskell
Они реализуются через примитивные операции в системе времени выполнения для чтения и записи в память.
Безопасность побочного действия разрушительной записи в память обеспечивается за счет использования монад для линеаризации доступа к изменяемому состоянию.
Глядя на primitive пакет для массивов Haskell (в IO или же ST), вы можете видеть, что реализации в терминах праймеров GHC:
-- | Create a new mutable array of the specified size and initialise all
-- elements with the given value.
newArray :: PrimMonad m => Int -> a -> m (MutableArray (PrimState m) a)
newArray (I# n#) x = primitive
(\s# -> case newArray# n# x s# of
(# s'#, arr# #) -> (# s'#, MutableArray arr# #))
-- | Read a value from the array at the given index.
readArray :: PrimMonad m => MutableArray (PrimState m) a -> Int -> m a
readArray (MutableArray arr#) (I# i#) = primitive (readArray# arr# i#)
-- | Write a value to the array at the given index.
writeArray :: PrimMonad m => MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray (MutableArray arr#) (I# i#) x = primitive_ (writeArray# arr# i# x)
То есть с точки зрения:
- newArray #
- readArray #
- writeArray #
которые являются примитивными (с аппаратным ускорением;) сервисами для работы с памятью, предоставляемой языковой средой исполнения.
Механизмы обеспечения безопасности типов для деструктивных эффектов памяти были введены в Haskell в статье Launchbury и Peyton-Jones, Lazy Functional State Threads, которая представляет ST монады и примитивы для изменяемых массивов.
Напоминаем, что "реализация с использованием монад", как это может быть сделано для различных структур управления, на самом деле не то же самое, что "побочные эффекты, изолированные монадическими операциями над непрозрачным типом", как в случае IO или же STгде свойства монады просто гарантируют, что чистый код остается таковым.
Изменяемые данные предоставляются как примитив времени выполнения, как объясняет Дон Стюарт; единственное, что здесь реализовано с помощью монад, это безопасность типов.
Они реализованы так же, как на императивном языке; т.е. обновление на месте. Система типов гарантирует, что вы не можете делать с ними ничего "плохого".