2

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

您可能已经注意到，级别图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 级图之间的连接将是 type M.Map (Int, Int) Connection，因此图的边应该是 type M.Map (Int, Int) (M.Map (Int, Int) Connection)。这意味着 1 级图中的每条边都会返回 0 级图的内部节点之间的一组连接。
  • 同样，对于 n 级图，连接的类型应该是M.Map (Int, Int) <Type of connection for Level n-1 graph>。

编辑：实际上上述表示可以为我工作；我只需要以简化的形式存储边缘。但是有没有可能写出满足上述条件的程序呢？

4

1 回答 1

2

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

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
于 2013-09-21T20:02:26.787 回答