表示自动机的数据结构

Question

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

直观地说,拉链与树木接近的东西是完美的:那些算法是状态合并算法,它们在状态上保持某种焦点(蓝色条纹),因此可以从某种拉链中获益,快速达到有趣的点.但我有点失落,因为DFA(确定性有限自动机)更像是一个类似于树状结构的图形结构:过渡可以让你回到结构中,这不太可能使拉链正常.

所以我的问题是:你将如何表示DFA(或至少它的过渡),以便你可以快速操纵它？

Answer 1

让我先从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

这使您可以访问计算结构.它也是一个类别,但不是箭头.一旦它成为箭头,你就会在某处出现不透明的功能.

Answer 2

你能用图表开始吗？我认为fgl包是Haskell平台的一部分.

否则,您可以尝试使用'derived(Data)'定义自己的结构,并使用"Scrap Your Zipper"库来获取Zipper.