5

tying-the-knot 策略可用于构建图，例如，使用简单的两条边图作为示例：

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
4

3 回答 3

4

通常，您必须能够将节点与先前观察到的节点进行比较，以确定您实际上是在重新访问图的一部分，而不是陷入类似结构的子图。这与您如何在语法上表达节点或使用何种语言无关。

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

a - b
|   |
c - d

从

a - b
| /
c

或者

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

甚至

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

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

如果您将标识符（例如 int）添加到边缘或节点，或者您作弊并窃取标识符（例如地址，但在 Haskell 中由于 GC 而这不是确定性的），那么您可能能够使用这些信息来推断平等或不平等。

于 2015-10-15T23:19:54.710 回答
4

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

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

注意和以及和由相等的表达式定义，并将每一对作为一个底层对象实现是完全合法的。（这称为公共子表达式消除。）adbc

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

于 2015-10-15T23:21:43.330 回答
1

您可以观察共享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
于 2015-10-26T02:30:34.913 回答