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

Question

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

Waggle

You can not solve this problem without going outside the language. Your notion of a unique label, such as an integer, is one good refactoring of the problem into something solvable. – Jozef

Can the problem be solved on the case of labelled edges? I.e., a = Node (b,0) (c,0), representing that a is on the first slot of both b and c? – Waggle

If the labels are not globally unique, then you still get the problem that you cannot identify whether two nodes are distinct. – Equable

Check these questions: 1, 2. – Estevan

Answer 1

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.

Necessarily

Answer 2

In general you must be able to compare a node for equality with previously observed nodes to determine you are infact re-visiting a portion of the graph instead of having decended into a subgraph of similar structure. This is regardless of how you syntactically express your nodes or in what language.

For example, using either the provided representations it is not possible to distinguish a graph of

a - b
|   |
c - d

from

a - b
| /
c

or

a - b - c
|       |
d - e - f

or even

a - b                 a -
|   |   or heck even  |  |
- - -                  --

Each local observation is a node with two edges to indistinguishable entities.

If you either add an identifier, such as an int, to the edges or nodes, or you cheat and steal an identifier (such as an address, but in Haskell this isn't deterministic because of GC) then you might be able to use this information to infer equality or inequality.

Jozef

Answer 3

You can observe sharing in IO, using e.g. data-reify:

{-# LANGUAGE TypeFamilies #-}
import Data.Reify

data Node = Node Node Node
data NodeId s = NodeId s s

instance MuRef Node where
    type DeRef Node = NodeId
    mapDeRef f (Node n1 n2) = NodeId <$> f n1 <*> f n2

The implementation of countNodes is now trivial (but note that it is in IO!)

countNodes :: Node -> IO Int
countNodes n = do
    Graph nodes root <- reifyGraph n
    return $ length nodes

Your example:

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

*Main> print =<< countNodes square
4

Chadwick

What I love about these questions is they make me finally try out things like data-reify that I otherwise wouldn't get around to. – Chadwick