haskell - 表示自动机的数据结构

Question

我目前正在尝试提出一种数据结构，以满足我想在 Haskell 中实现的两种自动机学习算法的需求:RPNI和 EDSM .

直观上，类似于 zipper 之于树的东西将是完美的:这些算法是状态合并算法，它保持对状态的某种关注(蓝色边缘)，因此将受益于某种 zipper 来快速到达有趣的点。但我有点迷失了，因为 DFA(决定论有限自动机)更像是一种图形结构，而不是树状结构:转换可以让你回到结构中，这不太可能使 zipper 正常。

所以我的问题是:您将如何表示 DFA(或至少是其转换)，以便可以快速操作它？

Answer 1

让我从 Haskell 中自动机通常的不透明表示开始:

newtype Auto a b = Auto (a -> (b, Auto a b))

这代表一个函数，它接受一些输入并产生一些输出以及自身的新版本。为了方便起见，它既是类别又是箭头。它也是一个应用仿函数家族。不幸的是这种类型是不透明的。无法分析这个自动机的内部结构。但是，如果您用透明表达式类型替换不透明函数，您应该获得可以分析和操作的自动机:

data Expr :: * -> * -> * where
    -- Stateless
    Id      :: Expr a a

    -- Combinators
    Connect :: Expr a b -> Expr b c -> Expr a c

    -- Stateful
    Counter :: (Enum b) => b -> Expr a b

这使您可以访问计算的结构。它也是一个类别，但不是一个箭头。一旦它变成一个箭头，你就在某个地方有了不透明的函数。