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

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

你确实需要某种标签，因为从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是由相等的表达式定义的，并将每对实现为一个底层对象是完全合法的。(这称为公共子表达式消除。

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

Answer 2

一般来说，

您必须能够将节点与先前观察到的节点的相等性进行比较，以确定您实际上是在重新访问图的一部分，而不是被分解成类似结构的子图。 无论您如何语法表达节点或用哪种语言表达，这都是如此。

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

a - b
|   |
c - d

从

a - b
| /
c

或

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

甚至

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

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

如果您向边缘或节点添加标识符(例如 int(，或者欺骗并窃取标识符(例如地址，但在 Haskell 中由于 GC 而不确定(，那么您可以使用此信息来推断相等或不平等。

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