В Haskell, как сделать параметры только для чтения, зависящие от ST

Контекст: при рассмотрении сигнатуры функции на типичном императивном языке некоторые параметры могут быть обозначены как изменяемые ссылки, некоторые параметры могут быть обозначены как неизменяемые ссылки, некоторые параметры могут рассматриваться как простые чистые константы.

Я пытаюсь понять, как воспроизвести это в Haskell, самое главное - изменяемую / неизменяемую обработку переменных, которые зависят от состояния.

В Haskell есть несколько подходов к управлению состоянием. Один из подходов, кажется, основан на использовании _1 _ / _ 2 _ / _ 3_, который хорошо сочетается с преобразователями монад. Среди параметров функции с сохранением состояния, если я хочу явно указать, что один из них должен рассматриваться как неизменный внутри тела функции, я считаю, что ответы на этот вопрос: Создание функций только для чтения для состояния в Haskell хорошо объясните, как это сделать, используя Reader или MonadReader.

Другой подход к управлению состоянием (который меня больше интересует в данном случае) - это ST. Мне нравится ST больше, потому что он позволяет управлять более чем одной ячейкой памяти одновременно и кажется более производительным, чем State. Проблема в том, что я не знаю, как правильно различать изменяемые / неизменяемые переменные с состоянием в ST. Способ Reader в этом случае не подходит. Я смотрел на пакет STMonadTrans, который, кажется, помогает ST работать с преобразователями монад, но я не уверен, как его использовать.

Вопрос: У вас есть простой пример функции f, которая создает изменяемую переменную x с newSTRef и передает x функции g неизменным способом, то есть таким образом, что g может читать x, но не изменять x ? Если нет, есть ли обходной путь?

Замечание 1. Обходной путь может заключаться в том, чтобы заморозить изменяемые переменные перед их передачей, чтобы сделать их чистыми, однако в моем случае это неприемлемое решение, потому что замораживание может быть либо дорогостоящим, либо небезопасным, и невозможно быстро заморозить сложные структуры, такие как векторы векторов. Недопустимо и небезопасное принуждение. Я ищу безопасное решение с нулевой стоимостью выполнения.

Замечание 2: Кто-то сказал, что я могу просто прочитать ссылку, прежде чем переходить к функции, но это слишком упрощенный ответ на мой упрощенный вопрос. В более общем контексте, возможно, что нельзя readSTRef переменную x, прежде чем перейти к функции g, потому что x более сложен, как набор изменяемых массивов. Я все еще задаю свой вопрос таким простым способом, чтобы попытаться выяснить, как сделать общую вещь на простом примере.

Спасибо


state mutability haskell
person jam    schedule 03.06.2020    source источник
comment
Есть ли причина, по которой do { xVal <- readSTRef x; let result = fn xVal } не работает? xVal - это просто значение, поэтому fn может вызывать его, но не изменять, поскольку параметры функции не могут быть изменены в Haskell.   -  person bradrn    schedule 03.06.2020
comment
Вы должны привести пример того, какая конкретная ситуация вас интересует (на императивном языке / псевдокоде).   -  person leftaroundabout    schedule 03.06.2020
comment
@jam Учитывая то, как вы написали свой вопрос, я предположил, что вы хотите предотвратить изменение вызываемой функции fn x на writeSTRef. Если да, то код, который я дал, должен работать. Если нет, то что вы имели в виду?   -  person bradrn    schedule 03.06.2020
comment
@jam И в любом случае, если вы хотите иметь возможность вызывать readIORef, но не writeIORef, тогда у вас есть неизменное значение, и, насколько я понимаю, нет смысла использовать для этого STRef s a, а не просто a.   -  person bradrn    schedule 03.06.2020
comment
@bradrn Извините, я прочитал слишком быстро. Однако я понимаю, что это слишком узкий вариант использования. Я задавал простой вопрос, чтобы действительно получить ответ на гораздо более общий вопрос. Но этот вопрос настолько упрощен, что вы просто даете мне слишком простой ответ. Я заменю свой вопрос на массив или что-то в этом роде. Что бы вы сделали, если x более сложен, как массив, и вы хотите прочитать некоторые ячейки в нем   -  person jam    schedule 03.06.2020
comment
@jam Чтение ячейки из массива, вообще говоря, чистая операция. Обычно я ожидал бы функцию readCell :: Int -> Array a -> a; тогда я мог бы определить чистую функцию fn, используя это, и снова сделать do { array <- readSTRef arrayRef; let result = pureFnUsingReadCell array }. (1/2)   -  person bradrn    schedule 03.06.2020
comment
Это может быть проблема XY, которая довольно часто встречается, когда люди начинают изучать Haskell. . На вопрос типа как мне изменить состояние? наиболее идиоматическим ответом будет: Нет. Вы найдете другой способ моделирования проблемы, который лучше соответствует философии Haskell. Это не значит, что вы вообще не можете изменять состояние в Haskell. Есть ST, IORef и т. Д. Однако обычно они вам не нужны.   -  person Mark Seemann    schedule 03.06.2020
comment
(2/2) @jam Единственная ситуация, в которой это не сработает, - это если у вас есть изменяемый массив, а не неизменяемый массив внутри изменяемого STRef - но в этом случае я ожидал бы, что функции будут преобразовывать изменяемый в неизменяемый (например, freeze), что позволит вам сделать do { array <- freeze mutArray; let result = pureFnUsingReadCell array }.   -  person bradrn    schedule 03.06.2020
comment
@bradrn Да, именно так, у меня есть изменяемые массивы изменяемых массивов, что еще хуже. В своем замечании 1 я сказал, что мне не нравится это решение, потому что замораживание занимает O (n). Итак, я попробовал unsafeFreeze, который принимает O (1), но проблема в том, что у меня есть массив массивов, поэтому все еще O (n). Итак, я попробовал unsafeCoerce, но unsafeCoerce действительно небезопасен. Кажется, что все, что я пробую с ST, либо небезопасно, либо неэффективно. С State Reader - чистое решение.   -  person jam    schedule 03.06.2020
comment
@jam Неужели эффективность настолько важна, что вы не можете использовать функции O (n)? Я почти ничего не знаю о производительности, особенно в Haskell, но не могу не задаться вопросом, не является ли это случаем слишком ранней оптимизации. Возможно, попробуйте протестировать свое приложение (например, с помощью criterion) и посмотреть, действительно ли использование unsafeFreeze слишком медленное, чтобы использовал.   -  person bradrn    schedule 03.06.2020
comment
@MarkSeemann Проблема в том, что мой контекст очень специфичен, и его долго раскрывать здесь. Я пытаюсь реализовать дейкстру на графах. Многие стандартные алгоритмы графа обычно гораздо менее эффективны с неизменяемыми структурами с точки зрения памяти / времени выполнения. Так что я чувствую, что у меня нет особого выбора. Но в любом случае, даже без учета моего контекста, поскольку есть чистое решение для State, я не понимаю, почему не должно существовать чистого решения для ST   -  person jam    schedule 03.06.2020
comment
Думаю, теперь я лучше понимаю проблему @jam - спасибо за контекст! Есть ли причина, по которой вы не можете просто передать изменяемый массив прямо в свою функцию? Это немного теряет безопасность типов и допускает мутацию, что, безусловно, нежелательно, но похоже, что это сделает свою работу.   -  person bradrn    schedule 03.06.2020
comment
@bradrn Я могу это сделать, и я делал это до сих пор, и он работает, хотя и менее безопасен. Мой проект носит исключительно личный и исследовательский характер, просто для удовольствия, нет срочных результатов или чего-то еще, я просто пытаюсь писать стандартные алгоритмы наиболее эффективным и безопасным способом, которым я могу. Вот почему я пытаюсь найти более безопасный способ иметь дело с государством, когда это необходимо.   -  person jam    schedule 03.06.2020
comment
@jam Если подумать еще об этом, я вижу одно из возможных решений: вы можете создать свою собственную оболочку над изменяемым массивом - что-то вроде newtype STArray' p s i e = STArray' (STArray s i e). Затем определите data Mutation = CanMutate | CantMutate. Теперь, включив {-# LANGUAGE DataKinds #-}, вы можете иметь значения как STArray' CanMutate s i e, так и STArray' CantMutate s i e. Это позволит вам определить функцию-оболочку writeArray :: (Ix i) => STArray' CanMutate s i e -> i -> e -> ST s (), которая может применяться только к изменяемым массивам.   -  person bradrn    schedule 03.06.2020
comment
@jam (продолжение) И freeze :: STArray' CanMutate s i e -> STArray' CantMutate s i e просто перестает работать.   -  person bradrn    schedule 03.06.2020

Ответы (1)


arrow_upward
1
arrow_downward

Я не читал роман, который есть в разделе комментариев, но такой шаблон, как

newtype ReadOnly s a = ReadOnly (ST s a)

makeReadOnly :: STRef s a -> ReadOnly s a
makeReadOnly = ReadOnly . readSTRef

сослужил мне хорошую службу. Это классический прием: если вы хотите, чтобы тип данных поддерживал некоторые операции, просто определите тип данных как запись операций, которые вы хотите поддерживать. В данном случае он только один.

(В качестве бонуса из этого видно, что «переменные только для чтения» легко компонуются!)

person luqui    schedule 04.06.2020