結び固め戦略で構築されたグラフで検索することは可能ですか？戦略はかなり洗練され、私は方法を見つけることができなかったこと</p> <pre><code>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 </code></pre> <p>：

Question

結ぶ-ノット戦略は、一例として、単純な両刃グラフを使用して、などのグラフを構築することができますIntラベルなしで実際に使用することができます。たとえば、squareの値のノードの数を数える関数を書くにはどうすればよいですか？一般に

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

main = print $ countNodes square 
-- output: 4 

Answer 1

実際には、ハスケルの内部から書かれたようにノードを区別する方法がないので、何らかの種類のラベルが必要です。 Haskellのコンパイラは

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

を見たとき、それはaとdだけでなく、bとcは、同じ式で定義されていることに注意して、一つとして、各ペアを実装するために実際には、法的完全です基本オブジェクト。

実際、コンパイラが本当にそれをするのかどうかは疑問だが、実際には4つのすべてを識別することも合法であろうが、それらはまったく同じ意味（ "意味"無限木を書く本質的に異なる方法です。t = Node t t = Node (Node ... ...) (Node ... ...) - 意味的意味の観点から、のみボトムを含まないデータ型の値です。

Answer 2

あなたが代わりに類似の構造のサブグラフにdecendedたのグラフの一部を再訪問Infactはであるかを決定するために以前に観察されたノードと等価のノードを比較することができなければなりません。これは、構文的にノードをどのように表現するか、またどの言語で表現するかにかかわらずです。例えば、提供される表現のいずれかを使用することが

a - b 
|/
c 

又は

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

あるいは

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

から

a - b 
| | 
c - d 

のグラフを区別することが可能

しません

各ローカル観測は、区別できないエンティティに対して2つのエッジを持つノードです。

エッジやノードにintなどの識別子を追加するか、識別子（アドレスなど）を不正行為して盗んだ場合、ハスケルではGCのために決定的ではありません。この情報を使用して、平等または不平等を推測することができます。

Answer 3

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