Название шаблона типа: R a b = Q (a → (R a b, b))
Я ищу лексику здесь. Существует несколько форм, которые имеют общие имена. Например, 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. Рекурсивная функция делает ее немного похожей на государственную Монаду или Cont Monad. Это также единственная структура, кроме (->)
и (>=>)
, для которой я видел экземпляр Arrow.
Есть ли общее имя для этой структуры данных?
Ответы
Ответ 1
Это стрелка автомата, также известная как машина Мили. В вашем конкретном примере используется (->)
как основная стрелка; другой общий выбор Kleisli m
для некоторого монада m (который просто превращает a -> b
в a -> m b
, например, data R a b = Q (a -> MyMonad (b, R a b))
).
Он обычно используется в функциональном реактивном программировании (в частности, FRP с стрелкой - см., например netwire и эти два сообщения в блоге: 1, 2) и имеет приложения для общей обработки потока (например, iteratees).
Это похоже на сопрограмму во многих отношениях, но это более конкретная концепция. Два сообщения в блоге, которые я связал, назовут их сопрограммами, поэтому "сопрограмма", безусловно, является распространенным способом обращения к нему, но точное имя - это стрелка автомата.
Ответ 2
Я бы назвал эту структуру данных Coroutine.
Он выражает вычисление, которое можно контролировать параллельно с каким-либо другим вычислением, и которое может быть оценено пошагово. Хотя интерфейс, который вы представляете, не является точным интерфейсом, который используется для класса Coroutines в Haskell (более общий Coroutine также является monad-agnostic, что означает, что обернутая функция возвращает m (R a b, b)
, а сопрограммы не должны потреблять вход, в то время как вам всегда приходится кормить вычисление с помощью a
), это достаточно похоже.
Структура данных также представляет собой подмножество того, что называется Comonads.
Ответ 3
Этот тип выглядит связанным с типом, который я ожидал бы использовать для преобразователя - я бы только ожидал, что тип вывода будет моноидальным. В Википедии есть страница с определенным классом преобразователей, преобразователи конечного состояния, что должно стать хорошей отправной точкой для поиска литературы.