Utrzymanie stanu bez przydziału

Uczę się programowania funkcjonalnego i mam problem ze zrozumieniem, w jaki sposób niektóre konkretne scenariusze są wdrażane bez użycia przypisania. Poniższy prosty problem w zasadzie podsumowuje moje zamieszanie.

Napisz program, który odbiera zdarzenia dotyczące zmian w danej strukturze danych i emituje zdarzenia, gdy ta struktura danych osiągnie określony stan.

Mam więc kopię struktury danych, którą prowadzę

datastructure_copy::DataStructure 

Mam strumień zdarzeń, które są uruchamiane, gdy się zmieniają:

datastructure_changes::Stream Change

Mam funkcję, która stosuje zmianę w strukturze danych i zwraca nową kopię:

apply_change::Change -> DataStructure -> DataStructure

I mam predykat, który sprawdza, czy stan danych osiągnął pożądany stan.

is_ready::DataStructure ->Boolean

Innymi słowy, potrzebuję czegoś takiego jak „redukcja”, która działa na strumieniach.

Wiem, że jednym ze sposobów realizacji tego jest ponowne obliczenie stanu za każdym razem, gdy pojawia się zmiana, jednak wydaje się to niepraktyczne. Grałem trochę z monadą państwową, ale wydaje mi się, że ma ona rozwiązać inny problem.

Czy jest na to inny sposób?

Zauważ, że moje pytanie jest czysto koncepcyjne i nie znam się na Haskellu.

Wiem, że jednym ze sposobów realizacji tego jest ponowne obliczenie stanu za każdym razem, gdy pojawia się zmiana, jednak wydaje się to niepraktyczne.

Jeśli zmiany zastosowane w momencie wystąpienia zdarzenia nie są rozdzielne, w taki czy inny sposób, będziesz musiał ponownie obliczyć stan za każdym razem, gdy wystąpi zdarzenie, ponieważ stanem końcowym jest tylko stan początkowy plus kolejne zmiany. I nawet jeśli zmiany są rozdzielne, zazwyczaj chcesz sukcesywnie przekształcać stan w następny, ponieważ chcesz zatrzymać proces tak szybko, jak dany stan zostanie osiągnięty, i ponieważ musisz obliczyć następny stan, aby ustalić, czy nowy to stan poszukiwany.

W programowaniu funkcjonalnym zmiany stanu są zwykle reprezentowane przez wywołania funkcji i / lub parametry funkcji.

Ponieważ nie można przewidzieć, kiedy zostanie obliczony stan końcowy, nie należy używać funkcji rekurencyjnej innej niż końcowa. Strumień stanów, w którym każdy stan opiera się na poprzednim, może być dobrą alternatywą.

W twoim przypadku odpowiedziałbym na pytanie następującym kodem w języku Scala:

import scala.util.Random

val initState = 0.0
def nextState(state: Double, event: Boolean): Double = if(event) state + 0.3 else state - 0.1 // give a new state
def predicate(state: Double) = state >= 1

// random booleans as events
// nb: must be a function in order to force Random.nextBoolean to be called for each  element of the stream
def events(): Stream[Boolean] = Random.nextBoolean #:: events()  

val states: Stream[Double] = initState #:: states.zip(events).map({ case (s,e) => nextState(s,e)}) // a stream of all the successive states

// stop when the state is >= 1 ;
// display all the states computed before it stopped
states takeWhile(! predicate(_)) foreach println 

Co może na przykład dać (uprościłem wynik):

0.0
0.3
0.2
0.5
0.8

val states: Stream[Double] = ... to linia, w której obliczane są kolejne stany.

Pierwszym elementem tego strumienia jest stan początkowy systemu. zipscala strumień stanów ze strumieniem zdarzeń w pojedynczy strumień par elementów, z których każda jest parą (stan, zdarzenie). mapprzekształca każdą parę w pojedynczą wartość będącą nowym stanem, obliczoną jako funkcja starego stanu i powiązanego zdarzenia. Nowy stan jest zatem stanem uprzednio obliczonym oraz powiązanym zdarzeniem, które „modyfikuje” stan.

Zasadniczo definiujesz potencjalnie nieskończony strumień stanów, przy czym każdy nowy stan jest funkcją ostatniego obliczonego stanu i nowego zdarzenia. Ponieważ strumienie są leniwe w Scali (między innymi), są obliczane tylko na żądanie, więc nie musisz obliczać bezużytecznych stanów i możesz obliczyć tyle stanów, ile chcesz.

Jeśli interesuje Cię tylko pierwszy stan, który uwzględnia predykat, zamień ostatni wiersz kodu na:

states find predicate get

Który pobiera:

res7: Double = 1.1

Mówisz, że masz 2 funkcje:

apply_change::Change -> DataStructure -> DataStructure
is_ready::DataStructure ->Boolean

a jeśli dobrze cię rozumiem, to is_readyjest raczej drogi, więc nie chcesz tego robić przy każdym zdarzeniu zmiany w kółko.

Potrzebna jest funkcja, która przyjmuje początkową strukturę danych i kondensuje ją do stanu prostego, a funkcja przyjmuje stan skondensowany, Zmianę i generuje nowy stan skondensowany.

Powiedz DataStructure to tryplet x,y,zi czekasz, aż x, y i z będą liczbami pierwszymi. Twój stan skondensowany może wówczas być zbiorem, który z x, y, z nie jest liczbą pierwszą. Zmiana, która powoduje, że x liczba pierwsza usuwa x z zestawu. Zmiana, która powoduje, że x nie jest liczbą pierwszą, dodaje x do zestawu (jeśli nie występuje). DataStructure jest gotowa, a następnie zestaw jest pusty.

Pomysł polegałby na tym, że aktualizacja stanu skondensowanego jest o wiele tańsza niż aktualizacja DataStructure, a przetwarzanie jest już od zera.

Uwaga: Jeszcze lepszym podejściem może być śledzenie, które z x, y, z zostały sprawdzone jako pierwsze, a jeśli gdzie. Dla każdej zmiany oflagujesz odpowiednie pole jako niezaznaczone. Następnie, gdy nazywa się is_ready, sprawdzasz i zapamiętujesz. Jest to lepsze, jeśli nie sprawdzasz is_ready po każdej zmianie, ponieważ x może zmienić się wiele razy, a sprawdzasz tylko liczbę pierwszą.