Is it possible to do a search on a graph constructed with the tying-the-knot strategy?

The tying-the-knot strategy can be used to construct graphs such as, using a simple two-edged graph as an example:

data Node = Node Node Node

-- a - b
-- |   |
-- c - d
square = a where
    a = Node b c
    b = Node a d
    c = Node a d
    d = Node b c

That strategy is rather elegant, but I couldn't find a way to actually use it without Int labels. For example, how could I write a function that counts the amount of nodes on the square value?

countNodes :: Node -> Int
countNodes = ... ??? ...

main = print $ countNodes square
-- output: 4

Solution

You do indeed need some kind of labeling, because from inside Haskell there is no way to distinguish the nodes as written. Indeed, when a Haskell compiler sees

square = a where
    a = Node b c
    b = Node a d
    c = Node a d
    d = Node b c

it is entirely legal for it to note that a and d, as well as b and c, are defined by equal expressions, and to implement each pair as one underlying object. (This is called Common Subexpression Elimination.)

In fact, it would even be legal for it to identify all four, although I doubt compilers really do that as it would require noticing that they have the exact same semantic "denotation", being all essentially different ways of writing the infinite tree t = Node t t = Node (Node ... ...) (Node ... ...) - from the point of view of denotational semantics that's the only value of your datatype that doesn't contain bottoms.