Преобразуватели на крайни състояния в Haskell?

Машина 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

Awaiting е малко по-сложно от Read, защото Machine може да чете от множество източници. За Processes, които могат да четат само от един източник, 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. е детайл за изпълнение за работа с Sources. След като стана свидетел, че 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
    )

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

Универсалното количествено определяне на всички Monads 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 модели преобразуватели на състоянието.