haskell - Haskell 上的 Buchi 自动机/有限状态机实现

Question

对 Haskell 来说相当新，我必须实现一个 buchi 自动机

我最初的实现是这样的

data NBA s a = NBA { states        :: [s];
                     finalStates   :: [s];
                     initialStates :: [s];
                     delta         :: Data.Map s [(a, s)]}

使用 Data.Map 作为转换函数。所说的 map 正在做的是为给定状态返回一个包含元组 (a, s) 的列表，其中 a 是字母符号，s 是目标状态。

但是我最近看到有人实现了自动机，例如

data NBA s a = NBA { states        :: [s];
                 finalStates   :: [s];
                 initialStates :: [s];
                 delta         :: s -> [(a, s)]}

这将转换功能留给用户标准，他们可以使用他们想要的任何数据结构。对于虚拟示例，他们甚至可以使用模式匹配来定义增量。此外，所有与 buchi 一起使用的函数，例如 bfs 可以delta automaton s用来访问从 s 可到达的所有状态，而不是使用 Map.lookup。

这让我想知道制作 Buchi 自动机实现的最 Haskellish 方式是什么？

似乎第二种实现的一个明显缺点是删除状态。除非有不同的实现方式，例如删除一个状态

deleteState :: NBA -> s -> NBA
deleteState a s = { states = delete s (states a);
                    finalStates = delete s (states a);
                    initialStates = ...;
                    delta = filter (snd != s) (delta a)
                   }

在新的自动机中，每次调用delta都会伴随着过滤器的应用。

标签： haskell