如何比较递归数据结构？

Question

我有一个复杂的递归数据结构,我已简化为以下内容:

data Node = Node { value :: Integer, next :: Node } deriving (Show,Eq)

给出以下表达式:

--Create a circular structure
a = Node 1 b
b = Node 0 a --Tie the knot
c = Node 1 b --Another structure which points to b

表达式a和c在概念上是相同,但两者都代表保持该值1并指向表达式b的节点.我的问题是:如何在Haskell表达式中检查它们是否确实相等？如果我评估a == c它将继续永远评估循环结构中的子元素.

是否有可能在Haskell中执行这样的比较？

编辑:在我的情况下,我试图比较这两个用于检查/调试目的.但这样做的另一个原因可能是单元测试.

Answer 1

首先,a和b不相等,但a和c相等,不仅仅是概念上的,但它们实际上是相同的.

要回答您的问题:您的问题没有直接解决方案.如果您需要进行身份比较,首先必须建立身份概念.一种方法是使用Mapfrom键到节点:

data Node k =
    Node {
      nodeValue :: Integer,
      nodeNext  :: k
    }

这个想法是你有一个单独Map的类型k键到节点.但是,您无法Eq为该实例编写实例.解决这个问题的一种有点优雅的方法是使用反射:

{-# LANGUAGE ScopedTypeVariables #-}

import Data.Reflection

data Node n k =
    Node {
      nodeValue :: Integer,
      nodeNext  :: k
    }

instance (n `Reifies` Map k (Node n k)) => Eq (Node n k) where
    (==) = {- ... -}
        where
        nodeMap :: Map k (Node n k)
        nodeMap = reflect (Proxy :: Proxy n)

最近获得一些关注的另一个选择是可观察共享的概念.