为无限递归数据类型实现"Eq"/"Ord"

Question

我想要构建匹配字符串的NFA。我有：

data State = State Char State | Split State State | Final

注意，State可以是无限递归的，因为我想构建像下面这样的NFA：

-- NFA for regex `1*`
match1 = State '1' loop; loop = Split match1 Final

当对字符串执行这样的NFA时，我必须跟踪已经访问过的状态，以打破循环。我用Set来实现这一点，而CCD_2又需要State来实现Ord。然而，派生的Ord实例的compare当然也有同样的问题，即它一直在递归。

我该如何解决这个问题？我看过StableName，但makeStableName使用IOmonad，因此在实现compare(AFAIK)时无法使用。

我现在唯一能想到的就是向State添加某种id以进行跟踪：

data State = State Int Char State | Split Int State State | Final

但这感觉相当不合法，尤其是考虑到客户端代码必须确保其唯一性。

Answer 1

TL；DR：不要将State添加到Set，而是使用StableName State实现instance Hashable State，并添加到CCD16

正如评论中所指出的，如果不用某种唯一的id标记每个状态，这个问题就不容易解决。

我的第一次尝试是在State和Splitctor中添加一个Int，但这与NFA的构建方式不一致。由于这不是由客户端代码直接完成的，而是由构建器(解析器使用该构建器)完成的，后者必须自动生成唯一的id。

使用状态monad似乎是可能的，但问题是，实现会不断为已经是"monad"的状态生成新的唯一id；id'ed"；由于NFA中的循环。

最终将我推向正确方向的是在一条(现已删除)评论中提到Data.Reify。

Data.Reify依赖于StableNames和HashMap来检测周期，所以我想我可以通过在StableName的帮助下为State实现Hashable来做同样的事情。

以下是我的结局。

前言：

import qualified Control.Monad.State.Lazy as M
import Data.Hashable
import qualified Data.HashMap.Lazy as Map (empty, insert, lookup)
import Data.HashMap.Lazy (HashMap)
import System.IO.Unsafe (unsafePerformIO)
import System.Mem.StableName (eqStableName, makeStableName)

相关类型再次出现(因为我现在已经更改了它们)：

data State = State {accepts :: Match, next :: State}
| Split {left :: State, right :: State}
| Final
data Match = AnyChar
| LiteralChar Char
| CharRange (Char, Char)
deriving (Eq, Ord, Show)

Hashable的实施(需要Eq)；

instance Eq State where
x == y = unsafePerformIO $
M.liftM2 eqStableName (makeStableName x) (makeStableName y)
instance Hashable State where
hashWithSalt salt state = unsafePerformIO $
hashWithSalt salt <$> makeStableName state

我认为这种实现有三个可能的问题：

1. 相同的State在评估后可能具有不同的StableName。这是已知的StableName行为，在NFA执行期间没有问题，因为在最坏的情况下，当计算出在不消耗输入的情况下可到达的下一个可能状态时，Split将被跟踪两次
2. 通过相同的令牌，CCD_ 31可以针对相同的CCD_ 33返回CCD_。到目前为止，我还不知道其中的含义‍♂️
3. 我不知道unsafePerformIO在这种情况下有多安全。但我看到其他代码也做了类似的事情，Data.Reify文档说它应该是安全的

NFA执行的实现目前在存在循环的情况下工作，instance Show State的实现也是如此。