haskell - 如何比较递归数据结构？

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 相等，不仅在概念上，而且它们实际上是相同的东西。

回答您的问题:您的问题没有直接解决方案。如果你需要身份比较，你首先要建立一个身份的概念。一种方法是使用 Map从键到节点:

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

这个想法是你有一个单独的Map从类型 k 的键到节点。但是，您不能写 Eq例如那个。解决这个问题的一种优雅的方法是使用 reflection :

{-# 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)

最近引起关注的另一个选项是 observable sharing 的概念。 .