Как изменяемые массивы реализованы в Haskell? - PullRequest
Новая
       19

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

27 голосов
/ 25 апреля 2011

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

Ответы [ 3 ]

31 голосов
/ 25 апреля 2011

Как массивы, имеющие O (1) время для доступа или изменения индексированного элемента, реализованы в Haskell

Они реализованы посредством простых операций в системе времени выполнения для чтения и записи в память.

Безопасность побочного действия деструктивной записи в память обеспечивается использованием монад для линеаризации доступа к изменяемому состоянию.

Глядя на пакет primitive для массивов Haskell (в IO или ST), вы можете видеть, что реализации в терминах GHC's primops 

-- | 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 и примитивы для изменяемых массивов.

7 голосов
/ 25 апреля 2011

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

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

7 голосов
/ 25 апреля 2011

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

...