gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-02 18:30:56 24 4
gpt4 key购买 nike

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

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

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

最佳答案

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

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

关于haskell - 表示自动机的数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10516603/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com