Функционально-императивный гибрид

Question

Чистые функциональные языки программирования не допускают изменяемых данных, но некоторые вычисления более естественно / интуитивно выражаются императивным способом - или императивная версия алгоритма может быть более эффективной. Мне известно, что большинство функциональных языков не являются чистыми, и позволяют вам назначать / переназначать переменные и делать императивные вещи, но в целом это препятствует.

Мой вопрос: почему бы не разрешить манипулировать локальным состоянием в локальных переменных, а потребовать, чтобы функции могли обращаться только к своим собственным локальным и глобальным константам (или просто константам, определенным во внешней области видимости)? Таким образом, все функции сохраняют ссылочную прозрачность (они всегда дают одно и то же возвращаемое значение при одних и тех же аргументах), но внутри функции вычисление может быть выражено в императивных терминах (как, скажем, цикл while).

IO и все такое можно было бы выполнять обычными функциональными способами - через монады или передавая токен «мир» или «вселенная».

Answer 1

Краткий ответ: есть системы, позволяющие вам делать то, что вы хотите. Например, вы можете сделать это, используя монаду ST в Haskell (как указано в комментариях).

Монадный подход ST взят из Control.Monad.ST Хаскелла. Код, написанный в монаде ST, может использовать ссылки (STRef) там, где это удобно. Приятной особенностью является то, что вы даже можете использовать результаты монады ST в чистом коде, так как она по сути автономна (это в основном то, что вы хотели в этом вопросе).

Доказательство этого автономного свойства осуществляется через систему типов. Монада ST содержит параметр потока состояния, обычно обозначаемый переменной типа s. Когда у вас есть такое вычисление, вы получите монадический результат с типом:

foo :: ST s Int

Чтобы на самом деле превратить это в чистый результат, вы должны использовать

runST :: (forall s . ST s a) -> a

Вы можете прочитать этот тип как: дайте мне вычисление, где параметр типа s не имеет значения, и я могу вернуть вам результат вычисления без багажа ST. Это, в основном, препятствует выходу изменчивых переменных ST, так как они будут нести s с ними, что будет обнаружено системой типов.

Это может быть использовано для хорошего воздействия на чистые структуры, которые реализованы с помощью базовых изменяемых структур (например, vector package ). Можно отказаться от неизменности на ограниченное время, чтобы сделать что-то, что изменяет основной массив на месте. Например, можно объединить неизменный Vector с пакетом нечистых алгоритмов , чтобы сохранить большинство характеристик производительности алгоритмов сортировки на месте и при этом получить чистоту.

В этом случае это будет выглядеть примерно так:

pureSort :: Ord a => Vector a -> Vector a
pureSort vector = runST $ do
  mutableVector <- thaw vector
  sort mutableVector
  freeze mutableVector

Функции thaw и freeze имеют линейное копирование, но это не нарушит общее время выполнения O (n lg n). Вы даже можете использовать unsafeFreeze, чтобы избежать другого линейного обхода, поскольку изменяемый вектор больше не используется.

Answer 2

У меня вопрос: почему бы не разрешить манипулировать локальным состоянием в локальных переменных, а потребовать, чтобы функции могли обращаться только к своим собственным локальным и глобальным константам (или только константам, определенным во внешней области видимости)?

Хороший вопрос. Я думаю, что ответ заключается в том, что изменяемые локальные объекты имеют ограниченную практическую ценность, но изменяемые структуры данных, выделенные из кучи (в первую очередь, массивы), чрезвычайно ценны и образуют основу многих важных коллекций, включая эффективные стеки, очереди, наборы и словари. Таким образом, ограничение мутации только для местных жителей не дало бы чисто функциональному языку какого-либо важного преимущества мутации.

Относительно примечания, передача последовательных процессов, обменивающихся чисто функциональными структурами данных, предлагает многие преимущества обоих миров, потому что последовательные процессы могут использовать мутацию внутри, например, изменяемые очереди сообщений примерно в 10 раз быстрее любых чисто функциональных очередей. Например, это идиоматично в F #, где код в MailboxProcessor использует изменяемые структуры данных, но сообщения, передаваемые между ними, являются неизменяемыми.

Сортировка является хорошим примером в этом контексте. Быстрая сортировка Седжвика в C короткая и простая и в сотни раз быстрее, чем самая быстрая чисто функциональная сортировка на любом языке. Причина в том, что быстрая сортировка изменяет массив на месте. Изменчивые местные жители не помогут. Та же история для большинства графовых алгоритмов.