Jak skonstruować funkcję/typ, który obserwuje każde przejście w tym automatie stanów?

Question

Istotą moje pytanie jest, że mam deterministycznych automatów stanu, który jest na przechodzenie według listy ruchów i chcę to sekwencja przejścia służyć jako „obliczeniowej kontekście” dla innej funkcji. Ta inna funkcja obserwowałaby automat stanowy przy każdym przejściu i wykonałaby z niego pewne obliczenia, niejasno przypominając wzorzec widoku modelu. Trivially ta inna funkcja może po prostu odczytać bieżący stan, w którym znajduje się maszyna, i wydrukować ją na ekranie.

Moja implementacja machiny państwowej:

data FA n s = FA { initSt1 :: n, endSt1 :: [n], trans1 :: n -> s -> n } 

-- | Checks if sequence of transitions arrives at terminal nodes 
evalFA :: Eq n => FA n s -> [s] -> Bool 
evalFA fa@(FA _ sfs _) = (`elem` sfs) . (runFA fa) 

-- | Outputs final state reached by sequence of transitons 
runFA :: FA n s -> [s] -> n 
runFA (FA s0 sfs trans) = foldl trans s0 

i Przykład:

type State = String 
data Trans = A | B | C | D | E 

fa :: FA State Trans 
fa = FA ("S1") ["S4","S5"] t1 

-- | Note non-matched transitions automatically goes to s0 
t1 :: State -> Trans -> State 
t1 "S1" E = "S1" 
t1 "S1" A = "S2" 
t1 "S2" B = "S3" 
t1 "S2" C = "S4" 
t1 "S3" D = "S5" 
t1 _ _ = "S1" 

runFA fa [A,B] -- | S3 

Answer 1

mam zamiar podzielić tę odpowiedź w dwóch częściach. Pierwsza część odpowie na twoje oryginalne pytanie, a druga część odpowie na niedeterministyczne pytanie FSA, które zgłosiłeś w komentarzach.

Rury

Można użyć pipes do przeplatania efekty między obliczeń. Po pierwsze, zacznę z lekko zmodyfikowanej wersji kodu:

data FA n s = FA { initSt1 :: n, endSt1 :: [n], trans1 :: n -> s -> n } 

data State = S1 | S2 | S3 | S4 | S5 deriving (Eq, Show) 
data Trans = A | B | C | D | E deriving (Read) 

fa :: FA State Trans 
fa = FA (S1) [S4,S5] t1 

-- | Note non-matched transitions automatically goes to s0 
t1 :: State -> Trans -> State 
t1 S1 E = S1 
t1 S1 A = S2 
t1 S2 B = S3 
t1 S2 C = S4 
t1 S3 D = S5 
t1 _ _ = S1 

Jedyną różnicą jest to, że używam wyliczenie zamiast String dla State.

Następnie będę realizować swoje przejścia jako Pipe:

runFA :: (Monad m, Proxy p) => FA n s ->() -> Pipe (StateP n p) s n m r 
runFA (FA _ _ trans)() = forever $ do 
    s <- request() 
    n <- get 
    put (trans n s) 
    respond n 

Spójrzmy uważnie rodzaju Pipe:

() -> Pipe (StateP n p) s n m r 
       ^^^ 
        | | | 
'n' is the state -+ | | 
         | | 
      's's come in -+ +- 'n's go out 

Więc można myśleć o tym jak o effectful scanl. Odbiera strumień s s używając request i wysyła strumień n s używając respond. Może faktycznie przeplatać efekty bezpośrednio, jeśli chcemy, ale zamiast tego zlecę efekty innym etapom przetwarzania.

Kiedy sformułować go jako Pipe mamy luksus wyboru co nasi strumienie wejściowe i wyjściowe będzie.Na przykład, możemy połączyć wejście do nieczystych stdin i połączyć wyjście do nieczystych stdout:

import Control.Proxy 
import Control.Proxy.Trans.State 

main = runProxy $ execStateK (initSt1 fa) $ 
    stdinS >-> takeWhileD (/= "quit") >-> mapD read >-> runFA fa >-> printD 

to rurociąg przetwarzania obrazu, które można odczytać jako powiedzenie:

• Wykonaj następujące Pipe z stan początkowy: initSt
• Wartości strumieni ze standardowej przepustowości
• Przesyłaj strumieniowo, dopóki jedna z tych wartości nie zostanie ustawiona na "quit"
• Zastosuj read do wszystkich wartości, aby przekonwertować je na Trans es
• Uruchom je za pośrednictwem naszego skanowanie skończonego stanu automatu
• Print the State y, że automat emituje

Spróbujmy go:

>>> main 
A 
S1 
B 
S2 
C 
S3 
A 
S1 
quit 
S2 
>>> 

Zauważ, jak również zwraca ostateczny State, że nasz automat był w. Możesz następnie fmap swój test ove R to obliczenie, aby zobaczyć, czy to się skończyło w terminalu węzła:

>>> fmap (`elem` [S1, S2]) main 
A 
S1 
B 
S2 
C 
S3 
A 
S1 
quit 
True 

Alternatywnie, możemy podłączyć nasz automat do czystych wejść i wyjść, zbyt:

import Control.Proxy.Trans.Writer 
import Data.Functor.Identity 

main = print $ runIdentity $ runProxy $ runWriterK $ execStateK (initSt1 fa) $ 
    fromListS [A, C, E, A] >-> runFA fa >-> liftP . toListD 

Że rurociąg mówi:

• Uruchom to w ramach czystego obliczenia (tj. `RunIdentity) i wydrukować czysty wynik
• Zastosowanie Writer zapisywać wszystkie stany Odwiedziliśmy
• Korzystając State do śledzenia naszego aktualnego stanu
• RSS listę predefiniowanych przejściami czysto
• Uruchom te przejścia przez Nasz FSA
• Log wyjścia do Writer korzystając liftP określić, że kierowanie Writer

Spróbujmy to zbyt:

>>> main 
(S2,[S1,S2,S4,S1]) 

Który wyprowadza stan końcowy i listę odwiedzonych stanów.

ListT

Teraz było drugie pytanie, które podniesione, co jest jak robisz effectful niedeterministycznym obliczeń. Daniel był w rzeczywistości niepoprawny: możesz przeplatać efekty z niedeterminizmem również za pomocą pipes! Sztuką jest użycie ProduceT, która jest implementacją pipes z ListT.

Najpierw pokażę jak używać ProduceT:

fsa :: (Proxy p) => State -> Trans -> ProduceT p IO State 
fsa state trans = do 
    lift $ putStrLn $ "At State: " ++ show state 
    state' <- eachS $ case (state, trans) of 
     (S1, A) -> [S2, S3] 
     (S2, B) -> [S4, S5] 
     (S3, B) -> [S5, S2] 
     (S4, C) -> [S2, S3] 
     (S5, C) -> [S3, S4] 
     (_ , _) -> [S1] 
    return state' 

Powyższy kod mówi:

• Drukuj aktualny stan
• Bind wiele możliwych przejść non-deterministycznie
• Powrót nowy wybrany stan

Aby uniknąć ręcznego odejście państwa, będę owijać fsa w StateT:

import qualified Control.Monad.Trans.State as S 

fsa2 :: (Proxy p) => Trans -> S.StateT State (ProduceT p IO) State 
fsa2 trans = do 
    s <- S.get 
    s' <- lift $ fsa s trans 
    S.put s' 
    return s' 

Teraz mogę uruchomić generator na wielu przejściach z łatwością za pomocą mapM. Kiedy skończę, mogę skompilować go do Producer wykorzystaniem runRespondT:

use1 :: (Proxy p) =>() -> Producer p State IO() 
use1() = runRespondT $ (`S.execStateT` S1) $ do 
    mapM_ fsa2 [A, B, C] -- Run the generator using four transitions 

ta produkuje rury, której skutki są do wydrukowania Stwierdza przemierza i wyprowadza strumień stanów końcowych napotyka. Będę podłączyć wyjście do etapu drukowania, dzięki czemu możemy obserwować zarówno jednocześnie:

>>> runProxy $ use1 >-> printD 
At State: S1 
At State: S2 
At State: S4 
S2 
S3 
At State: S5 
S3 
S4 
At State: S3 
At State: S5 
S3 
S4 
At State: S2 
S1 

Możemy obserwować drogę automatu za to bierze i jak to cofa. Wydaje wydruki tam, gdzie obecnie jest po każdym kroku, a następnie emituje wszystkie 7 stanów końcowych, gdy tylko dotrze do nich.

Przepraszam, jeśli ten post jest trochę nieukończony, ale jest to najlepsze, co mogę zrobić w pośpiechu.