#arrays #haskell #state #monads #mutable
#массивы #хаскелл #состояние #монады #изменяемый #haskell
Вопрос:
Я прочитал много исследовательских работ на эту тему, и обычно в них утверждается, что массивы реализованы с использованием монад. Но ни в одной из этих статей не было дано четкого определения того, как должен быть определен сам массив «типа», они только дали определения для функций, использующих монады для доступа или изменения этого типа. Как массивы, имеющие O (1) времени для доступа или изменения индексированного элемента, реализованы в Haskell ?! (например, STUArray и mArray)
Комментарии:
1. Обычно они реализуются путем обращения к внешней библиотеке или поддержке RTS.
2. Интересно, что может означать выражение «массивы реализованы с использованием монад»… Звучит как «хлеб выпекается с использованием таблиц».
3. @Alexey «внедренный» по-английски означает «введенный в действие». Так что нет ничего плохого в том, чтобы сказать, что изменчивость массивов в Haskell реализуется («вводится в действие» или «достигается») с помощью Монад. Тот же результат может быть достигнут с помощью бесконечных потоков, но это гораздо менее интуитивно.
Ответ №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 и Пейтон-Джонса «Потоки ленивого функционального состояния«, в которой представлены ST монада и примитивы для изменяемых массивов.
Ответ №2:
В качестве отступления, пожалуйста, имейте в виду, что «реализовано с использованием монад», как это может быть сделано для различных структур управления, на самом деле не то же самое, что «побочные эффекты, изолированные монадическими операциями над непрозрачным типом», как с IO или ST , где свойства монады просто гарантируют, что чистый код остается таким.
Изменяемые данные предоставляются как примитив среды выполнения, как объясняет Дон Стюарт; единственное, что здесь «реализовано с помощью монад», — это безопасность типов.
Комментарии:
1. Типобезопасная инкапсуляция и последовательность (
sпараметр, который автоматически передается в поток, задавая порядок зависимостей от эффектов).2. @Don: Ах да, я полагаю, я думал, что эта часть была достаточно очевидной, но вы правы, мне следовало быть более ясным.
Ответ №3:
Они реализованы таким же образом, как и в императивном языке; т.е. обновление на месте. Система типов гарантирует, что вы не сможете сделать с ними ничего «плохого».