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

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

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

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