haskell - 类型模式的名称 : 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))是状态单子(monad)的形式。

我想知道这样的形状是否有名称:

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

我在 Arrow 框架和状态机实现中看到了这种模式。递归函数让它感觉有点像 State Monad 或 Cont Monad。它也是除了 (->)之外的唯一结构和 (>=>)我已经看到了 Arrow 定义的一个实例。

这种数据结构有通用名称吗？

Answer 1

这是 automaton arrow ，也称为 Mealy 机器。您的具体示例仅使用 (->)作为基础箭头；另一个常见的选择是Kleisli m对于一些 monad m (它只是将 a -> b 变成 a -> m b ；例如， data R a b = Q (a -> MyMonad (b, R a b)) )。

常用在functional reactive programming (特别是带箭头的 FRP — 参见，例如 netwire 和这两篇博文:1 ，2)，并且适用于一般流处理(如迭代器)。

它在许多方面类似于协程，但它是一个更具体的概念。我链接的两篇博文称它们为协程，因此“协程”当然是一种常见的称呼方式，但准确的名称是自动机箭头。