是否有可能在搭配結戰略構建的圖上進行搜索？

捆紮-的結策略可以用於構造圖等，使用簡單的一柄圖爲例：是否有可能在搭配結戰略構建的圖上進行搜索？

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

來源

2015-10-15 MaiaVictor

你不能沒有語言之外去解決這個問題。您的獨特標籤（如整數）的概念是將問題重構爲可解的問題。 –

問題可以在標記邊緣的情況下解決嗎？即，a = Node（b，0）（c，0）'，表示'a'在'b'和'c'的第一個插槽上？ – MaiaVictor

如果標籤不是全局唯一的，那麼您仍然會遇到無法確定兩個節點是否不同的問題。 –

確實需要某種標籤，因爲從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，由相同的表達式定義，並落實到每一個對作爲一個基礎對象。（這被稱爲通用子表達式消除。）

事實上，它甚至可以合法識別全部四個，儘管我懷疑編譯器是否真的這樣做，因爲它需要注意到它們具有完全相同的語義「外延」，從無指示語義的角度來看，寫入無限樹t = Node t t = Node (Node ... ...) (Node ... ...)的所有本質上都是不同的方法，即只包含的不包含底部的數據類型的值。

來源

2015-10-15 23:21:43

一般來說，你必須能夠比較一個節點用於與先前觀察到的節點平等來確定你是INFACT再逛圖的一部分，而不是具有後裔居住成類似結構的一個子圖。這與您在語法上如何表達節點或使用何種語言無關。

例如，使用任一所提供的表示是不能夠從

a - b 
|/
c

或

區分的

a - b 
| | 
c - d

的曲線圖

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

甚至

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

每個本地觀察都是一個有兩條邊的節點，用於區分實體。

如果您向邊緣或節點添加標識符（例如int），或者欺騙並竊取標識符（例如地址，但是在Haskell中，由於GC而不確定），那麼您可能會能夠使用這些信息來推斷平等或不平等。

來源

2015-10-15 23:19:54

您可以使用例如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

來源

2015-10-26 02:30:34 Cactus

我喜歡這些問題的是他們讓我終於嘗試了像'data-reify'這樣的東西，否則我不會想到。 – Cactus

是否有可能在搭配結戰略構建的圖上進行搜索？

回答

相關問題