5

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

直观地说，接近于 zippers 对树的东西将是完美的：这些算法是状态合并算法，它们保持对状态的某种关注（蓝色边缘），因此将受益于某种 zippers 快速到达有趣的点。但我有点迷失了，因为 DFA（确定性有限自动机）更像是一种图形结构而不是树状结构：转换可以让你回到结构中，这不太可能使拉链正常。

所以我的问题是：你将如何表示一个 DFA（或者至少是它的转换），以便你可以快速地操纵它？

4

4 回答 4

9

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

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

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

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

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

于 2012-05-09T15:00:25.230 回答
5

您可以使用图表开始吗？我认为fgl包是 Haskell 平台的一部分。

否则，您可以尝试使用“派生（数据）”定义您自己的结构，并使用“Scrap Your Zipper”库来获取 Zipper。

于 2012-05-09T14:57:46.337 回答
0

如果您不需要任何花哨的图形算法，您可以将您的 DFA 表示为Map State State. 这使您可以快速访问和操作。您还可以通过跟踪当前状态来获得焦点。

于 2012-05-18T22:11:23.847 回答
0

看看regex-tdfa包：http ://hackage.haskell.org/package/regex-tdfa

源代码非常复杂，但它是带有标记 DFA 的正则表达式的实现，针对性能进行了调整，因此它应该说明一些有效表示 DFA 的良好实践。

于 2012-05-18T23:48:36.163 回答