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

我想构建匹配字符串的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来做这件事，它反过来需要State来实现Ord。然而，派生的Ord示例的compare当然也有同样的问题，它一直在递归。
我应该如何着手解决这个问题呢？我已经研究了StableName，但是makeStableName使用IO单子，因此在实现compare（AFAIK）时不能使用它。
我现在唯一能想到的就是在State中添加某种id以进行跟踪：

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

但这感觉相当不优雅，特别是考虑到客户端代码必须确保其唯一性。

- TL; DR：不要将State添加到Set，而是使用StableName State实现instance Hashable State，然后添加到HashSet。**

正如评论中所指出的，如果不给每个状态标记某种唯一的id，这个问题是不容易解决的。
我的第一次尝试是在State和Split ctor中添加一个Int，但是这与NFA的构建方式不太匹配，因为这不是由客户端代码直接完成的，而是由构建器（解析器使用构建器）完成的，构建器必须自动生成唯一的id。
使用状态单子似乎是可行的，但问题是，由于NFA中的循环，该实现将不断为已经"id 'ed"的状态生成新的唯一id。
最终把我推向正确方向的是在一条评论中提到了Data.Reify（现已删除）。
Data.Reify依赖于StableName s和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将被跟踪两次。

By the same token (==) might return False for the same State . I have no clue of the implications as of yet 🤷‍♂️
1.我不知道unsafePerformIO在这种情况下有多安全，但我看到过其他代码做类似的事情，Data.Reify文档含糊地说它应该是安全的。
NFA执行的实现目前在存在循环的情况下工作，instance Show State的实现也是如此。

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

1条答案

相关问题

热门标签

最新问答