是否有可能对搭配结战略构建的图进行搜索？ [英] Is it possible to do a search on a graph constructed with the tying-the-knot strategy?

问题描述

打结策略可用于构建图形，例如，使用简单的双边图形作为示例：

  data Node =节点节点节点
 
  -  a  -  b 
  -  | | 
  -  c  -  d 
 square = a其中
a =节点bc 
b =节点广告
c =节点广告
d =节点bc 
  

该策略相当优雅，但我找不到实际使用Int标签的方法。例如，我如何编写一个函数来计算 square 值的节点数量？

  countNodes :: Node  - > Int 
 countNodes = ... ??? ... 
 
 main = print $ countNodes square 
  -  output：4 
  

  square = a其中
a = Node bc 
b = Node ad 
c = Node ad 
d = Node bc 
  

完全注意 a 和 d ，以及 b 和 c 由相同的表达式定义，并将每一对实现为一个基础对象。 （这被称为通用子表达式消除。）



事实上，它确定全部四个都是合法的，尽管我怀疑编译器是否真的这样做，因为它需要注意到它们具有完全相同的语义外延，这是写入无限树的所有本质上不同的方式 - 从指称语义的角度来看，这是您的数据类型的 only 值，不包含底部。

The tying-the-knot strategy can be used to construct graphs such as, using a simple two-edged graph as an example:

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

That strategy is rather elegant, but I couldn't find a way to actually use it without Int labels. For example, how could I write a function that counts the amount of nodes on the square value?

countNodes :: Node -> Int
countNodes = ... ??? ...

main = print $ countNodes square
-- output: 4

解决方案

You do indeed need some kind of labeling, because from inside Haskell there is no way to distinguish the nodes as written. Indeed, when a Haskell compiler sees

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

it is entirely legal for it to note that a and d, as well as b and c, are defined by equal expressions, and to implement each pair as one underlying object. (This is called Common Subexpression Elimination.)

In fact, it would even be legal for it to identify all four, although I doubt compilers really do that as it would require noticing that they have the exact same semantic "denotation", being all essentially different ways of writing the infinite tree t = Node t t = Node (Node ... ...) (Node ... ...) - from the point of view of denotational semantics that's the only value of your datatype that doesn't contain bottoms.

这篇关于是否有可能对搭配结战略构建的图进行搜索？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！