Automat skończony w Haskell

Sprawdź kontrolkę./ Align = "left" / Transformator.Moduł automatu w pakiecie "strzałki". Typ wygląda tak

newtype Automaton a b c = Automaton (a b (c, Automaton a b c))

type Auto = Automaton (->)

Który używa funkcji jako podstawowej strzałki. Podstawianie ( - > ) dla "a" w definicji automatu i używając notacji infiksowej widać, że jest to mniej więcej równoważne:

newtype Auto b c = Automaton (b -> (c, Auto b c))

Innymi słowy automat jest funkcją, która pobiera dane wejściowe i zwraca wynik i nowy automat.

Możesz użyć tego bezpośrednio, pisząc funkcję dla każdego stanu, który pobiera argument i zwraca wynik i następną funkcję. Na przykład, oto maszyna stanowa do rozpoznawania wyrażeń regularnych "A+b" (to znaczy serii co najmniej jednego "a", po której następuje "b"). (Uwaga: kod nieprzetestowany)

state1, state2 :: Auto Char Bool
state1 c = if c == 'a' then (False, state2) else (False, state1)
state2 c = case c of
              'a' -> (False, state2)
              'b' -> (True, state1)
              otherwise -> (False, state1)

Jeśli chodzi o Twoje pierwotne pytanie, Q = {state1, state2}, X = Char, delta to zastosowanie funkcji, A F to przejście stanu zwracające True (zamiast "akceptującego stanu" użyłem przejścia wyjściowego z akceptującą wartością).

Alternatywnie można użyć notacji strzałek. Automaton jest instancją wszystkich interesujących klas strzałek, w tym pętli i obwodu, dzięki czemu można uzyskać dostęp do poprzednich wartości za pomocą opóźnienia. (Uwaga: ponownie, kod nieprzetestowany)

recognise :: Auto Char Bool
recognise = proc c -> do
   prev <- delay 'x' -< c   -- Doesn't matter what 'x' is, as long as its not 'a'.
   returnA -< (prev == 'a' && c == 'b')

Strzałka "delay" oznacza, że "prev" jest równa poprzedniej wartości "c", a nie bieżącej wartości. Możesz również uzyskać dostęp do poprzedniego wyjścia używając "rec". Na przykład, tutaj jest strzałka, która daje rozkładający się razem w czasie. (Faktycznie Przetestowane w tym przypadku)

-- | Inputs are accumulated, but decay over time. Input is a (time, value) pair.
-- Output is a pair consisting
-- of the previous output decayed, and the current output.
decay :: (ArrowCircuit a) => NominalDiffTime -> a (UTCTime, Double) (Double, Double)
decay tau = proc (t2,v2) -> do
      rec
         (t1, v1) <- delay (t0, 0) -< (t2, v)
         let 
            dt = fromRational $ toRational $ diffUTCTime t2 t1
            v1a = v1 * exp (negate dt / tau1)
            v = v1a + v2
      returnA -< (v1a, v)
   where
      t0 = UTCTime (ModifiedJulianDay 0) (secondsToDiffTime 0)
      tau1 = fromRational $ toRational tau

Zauważ, że wejście do " delay "zawiera" v", wartość pochodzącą z jego wyjścia. Umożliwia to klauzula "rec", dzięki czemu możemy zbudować pętlę sprzężenia zwrotnego.