Название типа шаблона: R a b = Q (a -> (R a b, b))

Question

Я ищу словарный запас здесь. Есть ряд фигур, которые имеют общие названия. Например, L a = Empty | Cons a L обычно называется «списком», тогда как T a = Leaf a | Node (T a) (T a) является «двоичным деревом», а St s a :: St (s->(a,s)) является формой Государственной монады.

Я хотел бы знать, имеет ли такая форма имя:

data  R a b = Q (a -> (R a b,b))

Я видел этот шаблон в реализациях Arrow и State Machine. Рекурсивная функция заставляет ее чувствовать себя как государственная монада или конт монада. Это также единственная структура, кроме (->) и (>=>), для которой я видел определенный экземпляр Arrow.

Есть ли общее название для этой структуры данных?

Answer 1

Это автоматная стрелка , также известная как машина Мили. Ваш конкретный пример просто использует (->) в качестве базовой стрелки; другой общий выбор - Kleisli m для некоторой монады m (которая просто превращает a -> b в a -> m b; например, data R a b = Q (a -> MyMonad (b, R a b))).

Обычно используется в функционально-реактивном программировании (в частности, FRP со стрелками - см., Например, netwire и эти два сообщения в блоге: 1 , 2 ) и имеет приложения для общей потоковой обработки (например, итераторы).

Во многих отношениях это похоже на сопрограмму, но это более конкретная концепция. Два сообщения в блоге, которые я связал, называют их сопрограммами, так что «сопрограмма», безусловно, является обычным способом обозначения этого слова, но точное название - автоматная стрелка.

Answer 2

Я бы назвал эту структуру данных сопрограммой.

Она выражает вычисление, которым можно управлять параллельно с некоторыми другими вычислениями, и которое можно оценивать пошагово.Хотя представленный вами интерфейс не является точным интерфейсом, который используется для класса сопрограмм в Haskell (более общий сопрограмм также не зависит от монады, что означает, что упакованная функция возвращает m (R a b, b), и сопрограммам не нужно потреблятьinput, хотя здесь вы всегда должны кормить вычисление a), оно достаточно похоже.

Структура данных также представляет собой подмножество так называемых Comonads.

Answer 3

Этот тип выглядит связанным с типом, который я ожидал бы использовать для преобразователя - я бы ожидал, что тип вывода будет моноидальным. В Википедии есть страница, посвященная определенному классу преобразователей, преобразователям конечного состояния , которые должны стать хорошей отправной точкой для поиска литературы.