How do I compare recursive data structures?

Question

I have a complex and recursive data structure which I have simplified to the following:

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

Given the following expressions:

--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

The expressions a and c are conceptually equal: they both represent a node which holds the value 1 and points to the expression b. My question is: how do I check that they are indeed equal in a Haskell expression? If I evaluate a == c it will keep evaluating sub-elements in the circular structure forever.

Is it possible to perform such a comparison in Haskell?

EDIT: In my case, I am trying to compare the two for inspection/debugging purposes. But another reason to do this could be for unit testing.

Answer 1

First of all, a and b are not equal, but a and c are equal, not just conceptually, but they are in fact the same thing.

To answer your question: there is no drop-in solution to your problem. If you need identity comparison, you first have to establish a notion of identity. One way to do this is to have a Map from keys to nodes:

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

The idea is that you have a separate Map from keys of type k to nodes. However, you can't write an Eq instance for that one. A somewhat elegant way to solve this is to use 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)

Another option that gained some attention recently is the notion of observable sharing.