论文标题
单声道表达及其衍生物
Monadic Expressions and their Derivatives
论文作者
论文摘要
由于Brzozowski，Antimirov或Lombardy和Sakarovitch，我们提出了对众所周知的衍生品计算的另一种解释，以便使用MONAD的notion抽象基础数据结构（例如集合或线性组合）。作为这种概括优势的一个例子，我们基于分级模块单元引入了一种新的推导技术。 我们还将定义表达式的运算符扩展到任何N- ARY功能，而不是价值集，例如经典操作（例如布尔重量的否定或交叉点）或更多异国情调的功能（例如代数为理性权重）。 此外，我们介绍了如何使用自动机的Colcombet和Petrisan分类定义从这种扩展表达式中计算（非必要有限的）自动机。这些类别理论的概念使我们能够以统一的方式执行这种结构，无论基本的单一单元如何。 最后，为了说明我们的工作，我们使用功能编程的高级技术提出了这些概念的Haskell实现，并提供了一个Web界面来操纵具体示例。
We propose another interpretation of well-known derivatives computations from regular expressions, due to Brzozowski, Antimirov or Lombardy and Sakarovitch, in order to abstract the underlying data structures (e.g. sets or linear combinations) using the notion of monad. As an example of this generalization advantage, we introduce a new derivation technique based on the graded module monad. We also extend operators defining expressions to any n-ary functions over value sets, such as classical operations (like negation or intersection for Boolean weights) or more exotic ones (like algebraic mean for rational weights). Moreover, we present how to compute a (non-necessarily finite) automaton from such an extended expression, using the Colcombet and Petrisan categorical definition of automata. These category theory concepts allow us to perform this construction in a unified way, whatever the underlying monad. Finally, to illustrate our work, we present a Haskell implementation of these notions using advanced techniques of functional programming, and we provide a web interface to manipulate concrete examples.
