我正在尝试用Haskell编写一个程序，该程序返回从初始状态开始的可访问状态列表，类似于深度优先搜索。
states_reachable :: Eq st => DFA st -> [st]
states_reachable (qs, sigma, delta, s, inF) =
[delta q a | q <- qs, a <- sigma]
注：
- qs是一组状态
- 西格玛是字母表
- delta是一个转换函数，它接受一个状态和一个符号并返回下一个状态
- s是初始状态
- inF是一个函数，如果状态为可接受状态，则返回true，否则返回false
正如现在定义的功能：
[delta q a | q <- qs, a <- sigma]
返回DFA中的所有状态（这是不正确的）。
我想要的是从初始状态s开始填充列表，并用每个输入测试delta函数。
例如：
// returns the states reachable from the initial state for all symbols in sigma
[delta s a | a <- sigma]
下一步是对添加到列表中的每个新状态重复该过程。这可能会添加重复项，但我可以稍后删除它们。
然后我尝试了：
[delta q a | q <- [delta s a | a <- sigma], a <- sigma]
我认为这可能有效，但没有，因为它创建了内部列表，然后使用它填充外部列表，然后停止。
我需要通过探索delta函数返回的所有新状态来递归地构建这个列表。
您试图在这里计算关系的传递闭包，其中关系是"x可以一步到达y"。因此，我建议使用通用的传递闭包解决方案，而不是DFA特定的解决方案，然后从DFA中生成该关系。这里有一个相当基本的方法：
module Closure (closure) where
import Data.List (nub)
closure :: Eq a => (a -> [a]) -> a -> [a]
closure nexts init = go [init]
where go xs = let xs' = nub $ xs ++ (xs >>= nexts)
in if xs == xs'
then xs
else go xs'
这里的算法是有一个可到达状态的列表，在每一步都通过从每个状态走到其所有最近的邻居来扩展它，然后nub列表以消除重复。一旦该扩展步骤没有添加新节点，就完成了。
现在，如何将DFA问题映射到这个问题上？这并不太难：您只需要使用sigma和delta生成一个nexts函数。在这里，我们需要假设您的DFA delta函数是total，即每个节点都为sigma中的每个字母指定了一个转换。这很容易，只需创建一个额外的"失败"节点，如果所有节点不喜欢自己的输入，它们都可以转换到该节点，所以我假设已经完成了。
neighbors :: (node -> letter -> node) -> [letter] -> node -> [node]
neighbors delta sigma n = map (delta n) sigma
有了这个，你原来的问题就减少到：
closure (neighbors delta sigma) s