我正在实施R7RS-small Scheme并且我遇到了以下问题,实现了相等的？:(应该是显而易见的)相等？测试值相等,它还能够测试循环数据结构的相等性,而不会进入无限循环.但是,因为我在Haskell中实现Scheme,所以我无法访问可以在哈希表*或搜索树结构中使用的可以转换为整数的基础指针值来跟踪我已经遵循的节点(以便能够有效地修剪会导致无限循环的路径).
相反,我似乎必须使用的是身份的相等性(通过(==)在IOArrays底层对,向量和记录上测量),因此看起来我所能做的就是构建列表,标记我遵循的节点(已分离)通过类型),然后对于我追随的每个其他节点,搜索我已经遵循的节点的适当列表,从我看来,它在时间上的O(n log n)和空间中的O(n)中缩放.
我是对的,鉴于这些条件,这是我可用的唯一算法,还是我缺少其他更有效的实现？
我已经考虑使用可以在搜索树或哈希表*中使用的标记标记每个可以包含引用的值,但是这里的问题是这对列表来说特别是空间效率低,因为我需要使用两个单词每个节点的标记,一个是ThreadId,一个是每个线程的唯一ID(ThreadId是必要的,因为我正在做一个Scheme的多线程实现,否则我必须保护一个MVar后面的共享唯一ID计数器或TMVar,在许多用例中会引起可怕的争用).
*当我在实现MonadIO的monad变换器中实现所有内容时,我可以使用传统的命令式哈希表.