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
最佳答案
您确实需要某种标签,因为从 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 ... ...)
-从指称语义的角度来看,这是您的数据类型中唯一不包含底部的值。
关于haskell - 是否可以在使用 tying-the-knot 策略构建的图上进行搜索?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33159805/