Как изменяются массивы, реализованные в Haskell?

Я читал много исследований по этой теме, и они обычно утверждают, что массивы реализованы с использованием Monads. Но ни одна из этих статей не дала четкого определения того, как должен определяться "тип" массива, они только дают определения для функций, использующих монады, для доступа или изменения этого типа. Как массивы, имеющие O (1) время для доступа или изменения индексированного элемента, реализованного в Haskell?! (например, STUArray и MArray)

Ответы

Ответ 1

Как массивы, имеющие 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 для изменяемых массивов.

Ответ 2

Они реализуются так же, как и на императивном языке; то есть обновление на месте. Система типов гарантирует, что вы не сможете сделать с ними что-либо "плохое".

Ответ 3

Как что-то в стороне, пожалуйста, имейте в виду, что "реализовано с использованием монад", как это может быть сделано для различных структур управления, на самом деле не то же самое, что "побочные эффекты, изолированные монодическими операциями на непрозрачном типе", с IO или ST, где свойства монады просто гарантируют, что чистый код остается таким.

Изменчивые данные предоставляются в качестве примитива времени выполнения, как объясняет Дон Стюарт; единственное, что реализовано с монадами, - это безопасность типов.