Name of type pattern: R a b = Q (a -> (R a b,b))

Question

I am looking for some vocabulary here. There are a number of shapes that have common names. For example L a = Empty | Cons a L Is generally called a "list," while T a = Leaf a | Node (T a) (T a) is a "binary tree" and St s a :: St (s->(a,s)) is the form of the State Monad.

I would like to know if a shape like this has a name:

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

I've seen this pattern in Arrow frameworks and State Machine implementations. The recursive function makes it feel a little like a State Monad or a Cont Monad. It is also the only structure besides (->) and (>=>) for which I have seen an instance of Arrow defined.

Is there a common name for this data structure?

Answer 1

This is an automaton arrow, also known as a Mealy machine. Your specific example just uses (->) as the underlying arrow; another common choice is Kleisli m for some monad m (which just turns a -> b into a -> m b; for example, data R a b = Q (a -> MyMonad (b, R a b))).

It's commonly used in functional reactive programming (specifically, arrowised FRP — see, e.g. netwire and these two blog posts: 1, 2), and has applications to general stream processing (like iteratees).

It's similar to a coroutine in many ways, but it's a more specific concept. The two blog posts I linked call them coroutines, so "coroutine" is certainly a common way to refer to it, but the precise name is an automaton arrow.

Answer 2

I would call that data structure a Coroutine.

It expresses a computation that can be controlled in parallel to some other computation, and that can be evaluated step-wise. While the interface you present isn't the exact interface that is used for the class of Coroutines in Haskell (A more general Coroutine is also monad-agnostic, meaning that the wrapped function returns a m (R a b, b), and coroutines do not have to consume input, while you here always have to feed the computation with an a), it is similar enough.

The data structure also represents a subset of what is called Comonads.

Answer 3

That type looks related to the type I would expect to use for a transducer -- I would only expect that the output type be monoidal. Wikipedia has a page on a particular class of transducer, the finite state transducers, that should be a good launching point for a literature search.