java - 如何创建递归类型图(图的图)？

Question

我想创建一个图形结构，它也可以用来表示更高级别的图形。我认为这个问题最好通过一个图来表达:

正如您可能已经注意到的，级别图 n-1包含级别 n 的节点。不存在混合图，即图中的所有节点都具有相同的级别。

我的用例的另一个方面是节点基本上只是一个函数。因此，1 级图是函数的互连(想想神经网络)。

我还需要图的连接矩阵成为一个独立的对象，而不是节点的属性(即我需要一些对象来表示所有连接，而不是 Node.Next 作为每个节点上的属性)。

我想到的伪代码方法是:

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 级图的内部节点之间的一组连接。
• 同样，对于 n 级图，连接类型应为 M.Map (Int, Int) <Type of connection for Level n-1 graph> .

编辑:实际上，上述表示对我有用；我只需要以简化的形式存储边缘。但是否可以编写一个程序来满足上述条件呢？

Answer 1

您可以将图的节点表示为具有唯一标签和值的事物。这样，值可以是任意的(函数)，没有任何约束，并且标签用于标识节点。然后，您可以将图表示为两个映射:一个将节点标签映射到其值，另一个将节点标签映射到相邻节点。

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 类型的每个值都包含一个与它所包含的 Network 构造函数数量相同级别的图，这是由类型系统强制执行的。例如，可以使用构建 2 级图

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