Nombre del tipo de patrón: R a b = Q (a -> (R a b, b))

Question

Estoy buscando un poco de vocabulario aquí. Hay una serie de formas que tienen nombres comunes. Por ejemplo, L a = Empty | Cons a L se denomina generalmente "lista", mientras que T a = Leaf a | Node (T a) (T a) es un "árbol binario" y St s a :: St (s->(a,s)) es la forma de la mónada de estado.

me gustaría saber si una forma como esta tiene un nombre:

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

que he visto este patrón en los marcos de flecha e implementaciones de la máquina del Estado. La función recursiva hace que se sienta un poco como una Monad de estado o una Monad de Cont. También es la única estructura además de (->) y (>=>) para la que he visto una instancia de Arrow definida.

¿Hay un nombre común para esta estructura de datos?

Answer 1

Esta es una automaton arrow, también conocida como máquina Mealy. Su ejemplo específico solo usa (->) como flecha subyacente; Otra opción común es Kleisli m para algunos monad m (que acaba de convertir a -> b en a -> m b; por ejemplo, data R a b = Q (a -> MyMonad (b, R a b))).

Es comúnmente usado en functional reactive programming (específicamente, arrowised FRP - ver, por ejemplo netwire y estas dos entradas de blog: 1, 2), y tiene aplicaciones en el tratamiento general de corriente (como iteratees).

Es similar a una corutina en muchos aspectos, pero es un concepto más específico. Las dos publicaciones de blog que he vinculado las llaman corutinas, por lo que "coroutine" es ciertamente una forma común de referirse a él, pero el nombre exacto es una flecha de autómata.

Answer 2

Llamaría a esa estructura de datos una Coroutine.

Expresa un cálculo que se puede controlar en paralelo a algún otro cálculo, y que se puede evaluar paso a paso. Si bien la interfaz que presenta no es la interfaz exacta que se utiliza para la clase de Corutinas en Haskell (una Coroutine más general también es monad-agnóstica, lo que significa que la función envuelta devuelve m (R a b, b), y las corutinas no tienen que consumir entrada, mientras que usted siempre debe alimentar el cálculo con un a), es lo suficientemente similar.

La estructura de datos también representa un subconjunto de lo que se llama Comonads.

Answer 3

Ese tipo se ve relacionado con el tipo que esperaría usar para un transductor - Solo esperaría que el tipo de salida fuera monoidal. Wikipedia tiene una página en una clase particular de transductor, el finite state transducers, que debería ser un buen punto de partida para una búsqueda bibliográfica.