Название типа шаблона: 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 и реализации государственной машины. Рекурсивная функция делает ее немного похожей на государственную Монаду или Cont Monad. Это также единственная структура, кроме (->) и (>=>), для которой я видел экземпляр Arrow.

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

Answer 1

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

Это обычно используется в functional reactive programming (в частности, arrowised FRP - смотри, например netwire и эти две записи в блоге: 1, 2), и имеет приложения для общей обработки потока (например, iteratees).

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

Answer 2

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

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

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

Answer 3

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