haskell - 是否可以在使用 tying-the-knot 策略构建的图上进行搜索？

Question

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 上的节点数量？值(value)？

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 是由相等的表达式定义的，并将每一对作为一个底层对象实现是完全合法的。 (这称为公共(public)子表达式消除。)

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