Конечный автомат в Haskell

Ответ 1

Существуют два основных варианта:

• Явная функция delta :: Q -> X -> Q (или [Q] по мере необходимости), как предлагает Свен Хагер.
• Карта delta :: Map (Q, X) Q, например. используя Data.Map, или если ваши состояния/алфавит можно индексировать по возрастанию числа Data.Array или Data.Vector.

Обратите внимание, что эти два подхода в основном эквивалентны, можно конвертировать из версии карты в версию функции (это немного отличается из-за дополнительного Maybe от вызова lookup) относительно легко

delta_func q x = Data.Map.lookup (q,x) delta_map

(Или соответствующая версия в карри для функции поиска для любого типа отображения, который вы используете.)

Если вы строите автоматы во время компиляции (и поэтому знаете возможные состояния и можете их закодировать как тип данных), то использование версии функции дает вам лучшую безопасность типа, поскольку компилятор может проверить, что вы покрыли все случаи.

Если вы создаете автоматы во время выполнения (например, с пользовательского ввода), затем сохраняете delta в качестве карты (и, возможно, выполняете преобразование функции, как указано выше), и имея соответствующую проверку ввода, которая гарантирует правильность, чтобы fromJust является безопасным (т.е. на карте всегда есть запись для любого возможного кортежа (Q,X), поэтому поиск никогда не сбой (никогда не возвращается Nothing)).

Недетерминированные автоматы хорошо работают с параметром карты, потому что неудачный поиск такой же, как без состояния, чтобы идти, т.е. пустой список [Q], и поэтому нет необходимости в каких-либо специальных обработка Maybe после вызова join . maybeToList (join от Data.Monad и maybeToList от Data.Maybe).

С другой стороны, алфавит наиболее определенно необходим: так, как автомат получает вход.

Ответ 2

Проверьте модуль Control.Arrow.Transformer.Automaton в пакете "стрелки". Тип выглядит следующим образом:

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

Это немного запутанно, потому что это трансформатор стрелки. В простейшем случае вы можете написать

type Auto = Automaton (->)

Использует функции в качестве основной стрелки. Подставляя (- > ) для "a" в определение Automaton и используя нотацию infix, вы можете видеть, что это примерно эквивалентно:

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

Другими словами, автомат - это функция, которая принимает вход и возвращает результат и новый автомат.

Вы можете использовать это напрямую, написав функцию для каждого состояния, которое принимает аргумент и возвращает результат и следующую функцию. Например, вот конечный автомат, чтобы распознать регулярное выражение "a + b" (то есть серию по крайней мере одного "a", за которым следует "b" ). (Примечание: непроверенный код)

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)

В терминах вашего исходного вопроса Q = {state1, state2}, X = Char, delta - это приложение функции, а F - переход состояния, возвращающий True (вместо того, чтобы иметь "принимающее состояние", которое я использовал выходной переход с принимающим значением).

В качестве альтернативы вы можете использовать обозначение стрелки. Automaton - это экземпляр всех интересных классов стрелок, включая Loop и Circuit, поэтому вы можете получить доступ к предыдущим значениям с помощью задержки. (Примечание: опять же, непроверенный код)

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')

Стрелка "delay" означает, что "prev" равно предыдущему значению "c", а не текущему значению. Вы также можете получить доступ к своему предыдущему выпуску, используя "rec". Например, вот стрелка, которая дает вам затухающий итог с течением времени. (Фактически проверенный в этом случае)

-- | 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

Обратите внимание, что ввод "задержки" включает в себя "v", значение, полученное из его вывода. Предложение "rec" позволяет это, поэтому мы можем создать цикл обратной связи.