haskell - 从任意节点列表生成边

Question

data Edge v = Edge {source :: v, target :: v}
          deriving (Show,Eq,Ord)

data Graph v = Graph {nodes :: Set v, edges :: Set (Edge v)}
           deriving Show


instance Arbitrary v => Arbitrary (Edge v) where
    arbitrary = do s <- arbitrary
                   t <- arbitrary
                   return $ Edge {source = s, target = t}

instance (Ord v, Arbitrary v) => Arbitrary (Graph v) where
    arbitrary = aux `suchThat` validGraph
        where aux = do lNodes <- arbitrary
                       lEdges <- arbitrary
                       return $ Graph {nodes = fromList lNodes, edges = fromList lEdges}

我目前有这个来生成我的图表。 但是，通过在 ghci 上使用示例，我注意到它要么不生成边，要么生成单个边。 是否可以控制生成的边数？ 我该怎么做？

编辑:图表在以下情况下被视为有效: 1-一条边的源节点和目标节点存在。 2-一个节点不能是多个边的源。

Answer 1

安arbitrary value 是 Gen 中的一个值单子(monad)。您可以在这个 monad 中做更多的事情，而不仅仅是将 任意 值组合在一起。您可以执行任何其他 Gen 操作，包括 choose :

choose :: Random a => (a, a) -> Gen a

Generates a random element in the given inclusive range.

您可以使用 choose 生成其他随机值，而不仅仅是 arbitrary 值。

instance (Ord v, Arbitrary v) => Arbitrary (Graph v) where
    arbitrary = do
        nodes <- arbitrary
        let
            lNodes = toList nodes
            numNodes = length lNodes
            arbitraryEdge = do
                source <- elements lNodes
                target <- elements lNodes
                return $ Edge {
                    source = source,
                    target = target
                }
        numEdges <- choose (0, numNodes * numNodes)
        lEdges <- vectorOf numEdges arbitraryEdge
        return $ Graph {nodes = nodes, edges = fromList lEdges}

在生成大图时，这种简单的实现不是很有效。如果它不需要每次使用 elements 时都需要扫描列表以获取生成的值，那么它可能是图中节点数量更快的一个因素。