Return to Answer

This is neat, methinks.

A couple of questions/points:

1. Is the || any (== s') rs part of canReachExcluding necessary?
2. In the same definition, the part rs = reach1From s au \\ ex takes time linear in the size of ex. Using a set (or hash) instead of a list for ex would probably improve your running time significantly in practice. But of course, that'd likely be at the expense of the clarity of your beautiful program.
3. You are of course right that your program checks "states excluded in other branches". What you are "really" implementing is depth-first search (DFS) on the graph defined by the automaton, and so you might want to look for a more efficient (functional) implementation of DFS. In that case, you could either look at the Haskell Library implementation, or maybe just this quick-and-dirty approach.

This is neat, methinks.

A couple of questions/points:

1. Is the || any (== s') rs part of canReachExcluding necessary?
2. In the same definition, the part rs = reach1From s au \\ ex takes time linear in the size of ex. Using a set (or hash) instead of a list for ex would probably improve your running time significantly in practice. But of course, that'd likely be at the expense of the clarity of your beautiful program.
3. You are of course right that your program checks "states excluded in other branches". What you are "really" implementing is depth-first search (DFS) on the graph defined by the automaton, and so you might want to look for a more efficient (functional) implementation of DFS. In that case, you could either look at the Haskell Library implementation, or maybe just this quick-and-dirty approach.