Is it possible to do a search on a graph construct

问题:

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

回答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.

回答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.

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