Конечные государственные преобразователи в Haskell?

Question

Мне было интересно, есть ли способ определить и работать с датчиками конечного состояния в Haskell идиоматическим способом.

Вы можете использовать FST как генераторы (он генерирует выходные данные типа {x1,x2}), или как распознаватели (при условии ввода типа {x1, x2}, он распознает его, если он принадлежит рациональному отношению), или как переводчики (учитывая ленту ввода, она переводит ее в ленту вывода). Изменится ли представление в зависимости от подхода?

Возможно ли также смоделировать FST таким образом, чтобы вы могли его создать, указав правила переписывания? Например, создание DSL для моделирования правил переписывания, а затем создание функции createFST :: [Rule] -> FST,

Самые близкие, что я мог найти, это Кметт, Бьярнасон и Кашель machines библиотека: https://hackage.haskell.org/package/machines

Но я не могу понять, как моделировать FST с Machine, Я бы предположил, что правильный способ сделать это будет похож на то, как они определяют машины Мура и Мили: определить FST как другую сущность, но предоставить экземпляр Automaton чтобы иметь возможность использовать его как машину.

Я также нашел некоторые другие варианты, но они определяют это простым способом (как в https://hackage.haskell.org/package/fst). Это не сильно меня убеждает, так как мне интересно, есть ли лучший способ сделать это идиоматически, используя сильные стороны системы типов Хаскелла (например, как машины Мура и Мили определены в machines библиотека).

Answer 1

Mealy машина поочередно читает a из потока входов a и выводит b потоку выводов. Сначала читает, а затем выводит один раз после каждого чтения.

newtype Mealy a b = Mealy { runMealy :: a -> (b, Mealy a b) }

Moore машина попеременно выводит b потоку выводов и читает вход a из потока входов. Начинается с вывода b и затем читает один раз после каждого вывода.

data Moore a b = Moore b (a -> Moore a b)

FST либо читает с его ввода, пишет на его вывод, либо останавливается. Он может читать столько раз подряд, сколько захочет, или писать столько раз подряд, сколько захочет.

data FST a b
    = Read  (a -> FST a b)
    | Write (b,   FST a b)
    | Stop

Эквивалент FST из машины есть Process, Это определение немного распространено. Чтобы упростить обсуждение, мы забудем о Process а пока и исследуй это изнутри.

Базовый функтор

Чтобы описать, что такое Process то есть, мы собираемся сначала заметить шаблон на всех трех машинах до сих пор. Каждый из них рекурсивно ссылается на себя "что делать дальше". Мы собираемся заменить "что делать дальше" на любой тип next, Mealy машина, отображая вход на выход, также обеспечивает next машина для запуска.

newtype MealyF a b next = MealyF { runMealyF :: a -> (b, next) }

Moore машина, после вывода и запроса ввода, выясняет next машина для запуска.

data MooreF a b next = MooreF b (a -> next)

Мы можем написать FST так же. Когда мы Read из ввода мы выясним, что делать next в зависимости от входа. Когда мы Write на выходе мы также предоставим, что делать next после вывода. Когда мы Stop дальше делать нечего.

data FSTF a b next
    = Read  (a -> next)
    | Write (b,   next)
    | Stop

Этот шаблон устранения явной рекурсии неоднократно обнаруживается в коде на Haskell и обычно называется "базовым функтором". В пакете машин базовый функтор Step, По сравнению с нашим кодом, Step переименовал переменную типа для вывода в o что делать рядом с r читаю Await и писать в Yield,

data Step k o r
  = forall t. Await (t -> r) (k t) r
  | Yield o r
  | Stop

Await Это немного сложнее, чем Read потому что Machine Можно читать из нескольких источников. За Process ES, которые могут читать только из одного источника, k является Is применяется к определенному типу, который является доказательством второго типа Is первый тип. Для Process чтение входов a, k будет Is a,

data Step (Is a) o r
  = forall t. Await (t -> r) (Is a t) r
  | Yield o r
  | Stop

Экзистенциальное количественное определение forall t. это деталь реализации для работы с Source с. После свидетельства этого a ~ t это становится.

data Step (Is a) o r
  = forall t ~ a. Await (t -> r) Refl r
  | Yield o r
  | Stop

Если мы объединяем t с a и удалите Refl конструктор, который всегда одинаков, это выглядит как наш FSTF,

data Step (Is a) o r
  = Await (a -> r) r
  | Yield  o    r
  | Stop

Экстра r что делать дальше в Await что делать дальше, когда больше нет ввода.

Станок трансформер `MachineT`

Машина трансформаторная, MachineT делает Step выглядят почти как наши FST, Он говорит: "Машина работает над какой-то монадой m что делать в этой монаде, чтобы получить следующий Step, next что нужно сделать после каждого шага MachineT ".

newtype MachineT m k o = MachineT { runMachineT :: m (Step k o (MachineT m k o)) }

В целом, специализируется на наших типах, это выглядит как

newtype MachineT m (Is a) o = 
    MachineT m (
        Await (a -> MachineT m (Is a) o) (MachineT m (Is a) o)
      | Yield  o   (MachineT m (Is a) o)
      | Stop
    )

Machine это чистый MachineT,

type Machine k o = forall m. Monad m => MachineT m k o

Универсальная количественная оценка по всем Monad s m это еще один способ сказать, что вычисление ничего не нужно от базового Monad, Это можно увидеть, подставив Identity за m,

type Machine k o = 
    MachineT Identity (
        Await (a -> MachineT Identity k o) (MachineT Identity k o)
      | Yield  o   (MachineT Identity k o)
      | Stop
    )

Процессы

Process или же ProcessT это Machine или же MachineT который читает только один тип ввода a, Is a,

type Process    a b = Machine    (Is a) b
type ProcessT m a b = MachineT m (Is a) b

Process имеет следующую структуру после удаления всех промежуточных конструкторов, которые всегда одинаковы. Эта структура точно такая же, как наша FST, за исключением того, что добавлено "что делать дальше" в случае, если больше нет ввода.

type Process a b =
    Await (a -> Process a b) (Process a b)
  | Yield  b   (Process a b)
  | Stop

ProcessT вариант имеет m обернутый вокруг него так, чтобы он мог действовать в монаде на каждом шагу.

Process моделирует государственные преобразователи.