如何創建遞歸類型圖（圖的圖）？

我想創建一個圖表結構，它也可以用來表示更高級別的圖表。我認爲這個問題是通過人物的最佳表現： Recursive Graph 如何創建遞歸類型圖（圖的圖）？

正如你可能已經注意到，n-1級別的圖形中包含n等級的節點。沒有混合圖，即圖中的所有節點具有相同的級別。

我的用例的另一個方面是節點基本上只是一個函數。所以1級圖形是功能的互連（想想神經網絡）。我還需要圖的連接矩陣是一個獨立的對象，而不是節點的屬性（即我需要一些對象來表示所有連接，而不是每個節點上的屬性Node.Next）。

一個psedocode的方法，我已經記：

class Node<T>: 
    func :: T -> T //The function 'func' takes a value of type 'T' and returns another value of type 'T'. 

class Network<T where T is instance of Node> inherits Node<T2>: 
    ConnectionMatrix<T> matrix; 
    override/implement func :: T2 -> T2; 

//I'm applying some sort of pattern matching on types here: 
type ConnectionMatrix<Network<T>> = 
    Dictionary<Nerwork<T>, Dictionary<Nerwork<T>, ConnectionMatrix<T>>> 
type ConnectionMatrix<Node> = Dictionary<Node, Dictionary<Node, Integer>>

但是，正如你可以看到它是不完整的，因爲它的立場不能在我知道的任何語言來表示。

只要不是動態輸入，實現的語言就不應該成爲問題。

編輯： 以下解決方案（如在回答中所建議的）將不會受到我的設計工作：

data Connection = Connection { 
    weight :: Double, 
    length :: Int 
} deriving (Eq, Show) 

data Graph a = Graph { 
    nodes :: M.Map Int a, 
    edges :: M.Map (Int, Int) Connection 
} deriving (Eq, Show) 

data Network a = Simple a | Nested (Network (Graph a)) 
    deriving (Eq, Show)

的原因是，我需要一個加權圖這樣的：

兩個0級圖（即簡單節點）之間的連接與上面定義的Connection類型相同。
兩個1級圖形之間的連接將是M.Map (Int, Int) Connection類型，因此圖形的邊緣應該是M.Map (Int, Int) (M.Map (Int, Int) Connection)類型。這意味着級別1圖形中的每條邊都會返回級別0圖形的內部節點之間的一組連接。
同樣，對於Level n圖，連接類型應爲M.Map (Int, Int) <Type of connection for Level n-1 graph>。

編輯：其實上述表示法可以爲我工作;我只需要以縮小的形式存儲邊緣。但是有可能編寫一個程序來滿足上述條件嗎？

來源

2013-09-21 Likhit

您可以將圖的節點表示爲具有唯一標籤和值的東西。這樣，值可以是任意的（一個函數），沒有任何約束，標籤用於標識節點。然後，您可以將圖形表示爲兩個映射：一個將節點標籤映射到它們的值，另一個將節點標籤映射到相鄰節點。

import qualified Data.Set as S 
import qualified Data.Map as M 

data Graph l a = Graph 
    { nodes :: M.Map l a 
    , edges :: M.Map l (S.Set l) 
    }

如果你想用型靜電深處的網絡，你可以，如果你想有可變深度的網絡定義只是

type Graph0 l a = a 
type Graph1 l a = Graph l a 
type Graph2 l a = Graph l (Graph l a) 
-- etc

（我以爲是你想要的東西），你可以定義其中遞歸是不均勻的遞歸數據的類型，比如

data Network l a = Level0 a | LevelUp (Network l (Graph l a))

然後Network類型的每個值包含相同水平的曲線圖作爲數它包含的構造函數，這是由類型系統強制執行的。例如，一個2級圖可以使用

LevelUp . LevelUp . Level0 :: Graph l (Graph l a) -> Network l a

來源

2013-09-21 20:02:26

嘿，我剛剛編輯我的問題，給出這個解決方案不起作用的原因。但是，我必須說，我對網絡類型的簡潔性感到驚訝。我花了3個小時才弄清楚究竟發生了什麼（我對Haskell的Map和Set數據類型缺乏瞭解並沒有幫助）。 – Likhit

如何創建遞歸類型圖（圖的圖）？

回答

相關問題