Подтвердить что ты не робот

Поддержание сложного состояния в Haskell

Предположим, вы создаете довольно большую симуляцию в Haskell. Существует множество различных типов объектов, атрибуты которых обновляются по мере продвижения имитации. Скажем, ради примера, что ваши сущности называются обезьянами, слонами, медведями и т.д.

Каков ваш предпочтительный метод для сохранения состояний этих объектов?

Первый и самый очевидный подход, о котором я думал, был следующим:

mainLoop :: [Monkey] -> [Elephant] -> [Bear] -> String
mainLoop monkeys elephants bears =
  let monkeys'   = updateMonkeys   monkeys
      elephants' = updateElephants elephants
      bears'     = updateBears     bears
  in
    if shouldExit monkeys elephants bears then "Done" else
      mainLoop monkeys' elephants' bears'

Это уже уродливо, если каждый тип объекта явно указан в сигнатуре функции mainLoop. Вы можете себе представить, как это будет ужасно, если бы у вас было, скажем, 20 типов сущностей. (20 не является необоснованным для сложных симуляций.) Поэтому я считаю, что это неприемлемый подход. Но его спасительная благодать заключается в том, что функции типа updateMonkeys очень ясны в том, что они делают: они берут список обезьян и возвращают новый.

Итак, следующая мысль заключалась бы в том, чтобы перевернуть все в одну большую структуру данных, которая содержит все состояние, очищая таким образом подпись mainLoop:

mainLoop :: GameState -> String
mainLoop gs0 =
  let gs1 = updateMonkeys   gs0
      gs2 = updateElephants gs1
      gs3 = updateBears     gs2
  in
    if shouldExit gs0 then "Done" else
      mainLoop gs3

Некоторые предположили бы, что мы завершаем GameState вверх в State Monad и вызываем updateMonkeys и т.д. в do. Это здорово. Некоторые предпочли бы предложить нам очистить его функциональным составом. Также прекрасно, я думаю. (Кстати, я новичок в Haskell, так что, возможно, я ошибаюсь в некоторых из них.)

Но тогда проблема в том, что функции типа updateMonkeys не дают вам полезной информации из их сигнатуры типа. Вы не можете быть уверены, что они делают. Конечно, updateMonkeys - описательное имя, но это небольшое утешение. Когда я передаю объект god и скажу "пожалуйста, обновите мое глобальное состояние", я чувствую, что мы вернулись в императивный мир. Это похоже на глобальные переменные с помощью другого имени: у вас есть функция, которая делает что-то в глобальном состоянии, вы называете это, и вы надеетесь на лучшее. (Я полагаю, что вы все еще избегаете проблем с concurrency, которые будут присутствовать с глобальными переменными в императивной программе. Но meh, concurrency не является почти единственной ошибкой глобальных переменных.)

Еще одна проблема заключается в следующем: предположим, что объекты должны взаимодействовать. Например, у нас есть такая функция:

stomp :: Elephant -> Monkey -> (Elephant, Monkey)
stomp elephant monkey =
  (elongateEvilGrin elephant, decrementHealth monkey)

Скажите, что это вызвано в updateElephants, потому что там, где мы проверяем, есть ли какой-либо из слонов в топании диапазона любых обезьян. Как вы элегантно распространяете изменения как обезьян, так и слонов в этом сценарии? В нашем втором примере updateElephants принимает и возвращает объект god, поэтому он может влиять на оба изменения. Но это только путает воды дальше и усиливает мою мысль: с божественным объектом вы фактически просто изменяете глобальные переменные. И если вы не используете объект god, я не уверен, как вы распространяете эти типы изменений.

Что делать? Конечно, многие программы должны управлять сложным состоянием, поэтому я предполагаю, что есть некоторые известные подходы к этой проблеме.

Просто для сравнения, вот как я могу решить проблему в мире ООП. Там будут объекты Monkey, Elephant и т.д. У меня, вероятно, были бы методы класса для поиска в наборе всех живых животных. Может быть, вы можете искать по местоположению, по ID, что угодно. Благодаря структурам данных, лежащим в основе функций поиска, они оставались выделенными в куче. (Я принимаю GC или подсчет ссылок.) Их переменные-члены будут мутировать все время. Любой метод любого класса мог бы мутировать любое живое животное любого другого класса. Например. a Elephant может иметь метод stomp, который уменьшал бы здоровье переданного объекта Monkey, и не было бы необходимости передавать этот

Аналогично, в Erlang или другом актер-ориентированном дизайне вы могли бы решить эти проблемы довольно элегантно: каждый актер поддерживает свою собственную петлю и, следовательно, свое собственное состояние, поэтому вам никогда не нужен объект-бог. Передача сообщений позволяет одной активности объекта инициировать изменения в других объектах, не передавая кучу вещей полностью обратно в стек вызовов. Тем не менее, я слышал, что он сказал, что актеры в Haskell недовольны.

4b9b3361

Ответ 1

Ответ функциональное реактивное программирование (FRP). Это гибрид двух стилей кодирования: управление состоянием компонентов и зависящие от времени значения. Поскольку FRP на самом деле является целым семейством шаблонов дизайна, я хочу быть более конкретным: я рекомендую Netwire.

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

Хотя это звучит сложно и неэффективно, на самом деле это очень тонкий слой вокруг обычных функций. Шаблон проектирования, реализованный Netwire, вдохновлен AFRP (Программируемое функциональное реактивное программирование). Это, вероятно, достаточно разное, чтобы заслужить свое имя (WFRP?). Вы можете прочитать учебник.

В любом случае следует небольшая демонстрация. Ваши строительные блоки - это провода:

myWire :: WireP A B

Подумайте об этом как о компоненте. Это изменяющееся во времени значение типа B, которое зависит от изменяющегося во времени значения типа A, например частицы в симуляторе:

particle :: WireP [Particle] Particle

Это зависит от списка частиц (например, всех существующих в настоящее время частиц) и само по себе является частицей. Пусть используется предопределенный провод (с упрощенным типом):

time :: WireP a Time

Это изменяющееся во времени значение типа Time (= Double). Ну, это время само по себе (начиная с 0 отсчитывается от всякий раз, когда была запущена проводная сеть). Поскольку он не зависит от другого изменяющегося во времени значения, вы можете его подавать, как хотите, следовательно, полиморфного типа ввода. Существуют также постоянные провода (изменяющиеся во времени значения, которые не меняются со временем):

pure 15 :: Wire a Integer

-- or even:
15 :: Wire a Integer

Чтобы соединить два провода, вы просто используете категориальный состав:

integral_ 3 . 15

Это дает вам часы с постоянной скоростью в 15 раз (интеграл от 15 по времени), начиная с 3 (константа интеграции). Благодаря различным классам проводов очень удобно комбинировать. Вы можете использовать своих обычных операторов, а также аппликативный стиль или стиль стрелок. Хотите часы, начинающиеся с 10 и вдвое превышающие скорость реального времени?

10 + 2*time

Хотите, чтобы начальная частица (0, 0) с (0, 0) и ускорялась с (2, 1) в секунду в секунду?

integral_ (0, 0) . integral_ (0, 0) . pure (2, 1)

Хотите отобразить статистику, пока пользователь нажимает клавишу пробела?

stats . keyDown Spacebar <|> "stats currently disabled"

Это всего лишь небольшая часть того, что Netwire может сделать для вас.

Ответ 2

Я знаю, что это старая тема. Но сейчас я столкнулся с такой же проблемой, пытаясь реализовать упражнение по шифрованию Rail Fence от пользователя exercism.io. Очень неудовлетворительно видеть такую ​​общую проблему, которая испытывает такое слабое внимание в Haskell. Я не считаю, что для того, чтобы сделать что-то просто, как поддержание состояния, которое мне нужно, чтобы изучить FRP. Итак, я продолжил поиск в Интернете и нашел решение более простым: государственная монада: https://en.wikibooks.org/wiki/Haskell/Understanding_monads/State