是否可以对使用打结策略构建的图进行搜索？

Question

打结策略可用于构建图，例如，以简单的双边图为例：

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

该策略相当优雅，但如果没有 Int 标签，我找不到实际使用它的方法。例如，我如何编写一个函数来计算 square 值上的节点数量？

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

main = print $ countNodes square
-- output: 4

Answer 1

一般来说，您必须能够比较一个节点与之前观察到的节点是否相等，以确定您实际上是在重新访问图的一部分，而不是下降到具有相似结构的子图中。这与您在句法上如何表达节点或使用何种语言无关。

例如，使用提供的任何一种表示都无法区分

的图形

a - b
|   |
c - d

来自

a - b
| /
c

或

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

甚至

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

每个局部观察都是一个节点，具有两条边，无法区分实体。

如果您向边或节点添加标识符（例如 int），或者您欺骗并窃取标识符（例如地址，但在 Haskell 中这不是确定性的，因为GC) 那么您也许可以使用此信息来推断相等或不相等。

Answer 2

您确实需要某种标记，因为从内部 Haskell 无法区分写入的节点。事实上，当 Haskell 编译器看到

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

完全合法地注意到 a 和 d，以及 b 和 c , 由相等的表达式定义，并将每一对实现为 one 底层对象。（这称为公共子表达式消除。）

事实上，它甚至可以识别所有四个，尽管我怀疑编译器是否真的这样做，因为它需要注意它们具有完全相同的语义 "denotation"，都是本质上不同的方式编写无限树 t = Node t t = Node (Node ... ...) (Node ... ...) - 从指称语义的角度来看，这是不包含底部的数据类型的唯一值。

Answer 3

您可以观察 IO 中的分享，例如使用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

countNodes 的实现现在很简单（但请注意它在 IO 中！）

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

你的例子：

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

是否可以对使用打结策略构建的图进行搜索？

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

haskell

tying-the-knot