Я изучаю функциональное программирование, и у меня возникают проблемы с пониманием того, как некоторые конкретные сценарии реализуются без использования заданий. Следующая простая проблема в значительной степени подводит итог моей путаницы.
Напишите программу, которая получает события об изменениях в данной структуре данных и генерирует события, когда эта структура данных достигает определенного состояния.
Итак, у меня есть копия структуры данных, которую я поддерживаю
datastructure_copy::DataStructure
У меня есть поток событий, которые запускаются при его изменении:
datastructure_changes::Stream Change
У меня есть функция, которая применяет изменение к структуре данных и возвращает его новую копию:
apply_change::Change -> DataStructure -> DataStructure
И у меня есть предикат, который проверяет, достигло ли состояние данных желаемого состояния.
is_ready::DataStructure ->Boolean
Другими словами, мне нужно что-то вроде «уменьшить», которое работает на потоках.
Я знаю, что один из способов реализовать это - пересчитывать состояние каждый раз, когда приходит изменение, однако это кажется непрактичным. Я немного поиграл с Государственной монадой, но мне кажется, что она предназначена для решения другой проблемы.
Так есть ли другой способ сделать это?
Обратите внимание, что мой вопрос носит чисто концептуальный характер, и я не очень хорошо знаком с Haskell.
источник
Ответы:
Если изменения, применяемые при возникновении события, не являются распределительными, так или иначе, вам придется пересчитывать состояние каждый раз, когда происходит событие, так как конечное состояние - это не что иное, как начальное состояние плюс последовательные изменения. И даже если изменения носят дистрибутивный характер, вы, как правило, хотите последовательно преобразовать состояние в следующее, поскольку вы хотите остановить процесс так же быстро, как достигается заданное состояние, и поскольку вам нужно вычислить следующее состояние, чтобы определить, является ли новый разыскиваемый штат.
В функциональном программировании изменения состояния обычно представлены вызовами функций и / или параметрами функций.
Поскольку вы не можете предсказать, когда будет вычислено конечное состояние, вы не должны использовать нехвостовую рекурсивную функцию. Поток состояний, в котором каждое состояние основано на предыдущем, может быть хорошей альтернативой.
Так что в вашем случае я бы ответил на вопрос следующим кодом в Scala:
Который может дать, например (я упростил вывод):
val states: Stream[Double] = ...
это линия, где вычисляются последовательные состояния.Первым элементом этого потока является начальное состояние системы.
zip
объединяет поток состояний с потоком событий в один поток пар элементов, каждая из которых является (состояние, событие).map
преобразовывает каждую пару в одно значение, являющееся новым состоянием, вычисляемое как функция старого состояния и связанного события. Таким образом, новое состояние - это ранее вычисленное состояние плюс связанное событие, которое «изменяет» состояние.Таким образом, в основном вы определяете потенциально бесконечный поток состояний, каждое новое состояние является функцией последнего вычисленного состояния и нового события. Поскольку потоки в Scala ленивы (среди прочих), они вычисляются только по требованию, поэтому вам не нужно вычислять бесполезные состояния, и вы можете вычислять столько состояний, сколько захотите.
Если вас интересует только первое состояние, которое учитывает предикат, замените последнюю строку кода на:
Который извлекает:
источник
val states: Stream[Double]...
Вы говорите, у вас есть 2 функции:
и если я вас правильно понимаю, то
is_ready
это довольно дорого, так что вы не хотите делать это для каждого события изменения снова и снова.Что вам нужно, так это то, что функция берет начальную DataStructure и конденсирует ее в простое состояние, а функция принимает сжатое состояние, изменение и выводит новое сжатое состояние.
Скажем, DataStructure - триплет,
x,y,z
и вы ожидаете, что x, y и z будут простыми числами. Тогда ваше сжатое состояние может быть набором из которых x, y, z не являются простыми. Изменение, которое делает x простым, удаляет x из набора. Изменение, которое делает x не простым, добавляет x к набору (если его нет). DataStructure готова, тогда набор пуст.Идея заключалась бы в том, что обновление сжатого состояния намного дешевле, чем обновление DataStructure и вычислений с нуля.
Примечание. Еще более удачный подход - отслеживать, какие из x, y, z были проверены на предмет простоты, и были ли они где. Для каждого изменения вы отмечаете соответствующее поле как не отмеченное. Затем, когда вызывается is_ready, проверьте и запомните. Это лучше, если вы не проверяете is_ready после каждого изменения, поскольку x может меняться несколько раз, и вы проверяете простое число только один раз.
источник