Haskell FGL 在 DynGraph 上使用图形函数

Question

我的目标是处理形状的交集图。相交图有节点:R^n 中的形状，如果它们相交，则节点之间有一条边。

在 Haskell 中，实现一个函数，

makeIntersectionGraph :: DynGraph g => [Shape] -> g Shape ()
makeIntersectionGraph sh = ... begin with the empty graph and add nodes and edges as you walk
                       ... through all possible intersections

上面的编译和类型检查都很好。一个简单的事情应该是使用 labNodes 函数获取图形的节点。

getNodes sh = labNodes (makeIntersectionGraph sh)

请注意文档说明:

DynGraph: dynamic, extensible graphs. Dynamic graphs inherit all operations from static graphs but also offer operations to extend and change graphs.

和labNodes 是Graph 类的函数。所以上面应该有效。

但是，我得到了错误:

No instance for (Graph gr0) arising from a use of `labNodes'
    In the expression: labNodes (makeIntersectionGraph es)
    In an equation for `makeIntersectionGraphComplete':
        makeIntersectionGraphComplete es
          = labNodes (makeIntersectionGraph es)

DFN2Graph.hs:346:46:
    No instance for (DynGraph gr0)
      arising from a use of `makeIntersectionGraph'
    In the first argument of `labNodes', namely
      `(makeIntersectionGraph es)'
    In the expression: labNodes (makeIntersectionGraph es)
    In an equation for `makeIntersectionGraphComplete':
        makeIntersectionGraphComplete es
          = labNodes (makeIntersectionGraph es)

----更新----我找到了解决方案，但我不明白问题出在哪里。如果我改变类型

makeIntersectionGraph :: DynGraph g => [Shape] -> g Shape ()

到

makeIntersectionGraph ::  [Shape] -> G.Gr Shape ()

在哪里

import qualified Data.Graph.Inductive.PatriciaTree as G

然后

getNodes sh = labNodes (makeIntersectionGraph sh)

工作得很好。我仍然遇到的问题是，当所有 DynGraph 都可以访问相同的函数时，我不明白为什么有必要调用 DynGraph 的具体实现。

Answer 1

您正在使用两个函数:一个生成图表，一个使用图表。现在让我们简化类型并忽略 DynGraph/Graph 的区别。

makeGraph :: Graph g => [Shape] -> g Shape ()
makeGraph = undefined

consumeGraph :: Graph g => g Shape () -> [LNode Shape]
consumeGraph = undefined

f :: [Shape] -> [LNode Shape]
f = consumeGraph . makeGraph -- same as f x = consumeGraph (makeGraph x)

编辑:把它分开一点:

f :: [Shape] -> [LNode Shape] -- Note: no g!
f shapes = consumeGraph g
  where g :: Graph g => g -- This annotation is just illustrative
        g = makeGraph shapes

问题是 g 没有出现在 f 的类型签名中。可以想象，编译器可以选择满足限制的几种类型中的任何一种，但这是任意的，它不会这样做。

所有 Graph 共享相同函数的事实并不能真正回答这个问题。中间图会使用帕特里夏树还是普通树？它有所作为。想象一下，如果我们正在谈论像 Num 这样的类:我们可以使用 Int 或 Double 或 Integer 或 Decimal，每种都具有完全不同的性能和语义特征。

因此需要在某处指示您想要哪种类型。您的解决方案有效；如果您想保持 makeIntersectionGraph 的通用性，您可以使用内部类型注释，如下所示:

f' :: [Shape] -> [LNode Shape]
f' xs = consumeGraph (makeGraph xs :: G.Gr Shape)

这个问题经常出现。我认为它是“show .read”问题；那是类似的情况。我们在中间使用什么类型？ The Haskell '98 report has a section on "ambiguous types" ，这也解释了为什么当您尝试使用 Num 函数执行此操作时，此问题被默认规则屏蔽。

(请注意，在 GHCi 中，'98 报告中指定的 type defaulting rules are changed，这就是为什么 在 GHCi show .read 中没有给出类型错误.)

哦，我差点忘了 DynGraph/Graph。如果您查看 Haddock 或源代码，您会看到 DynGraph 被定义为 class Graph gr => DynGraph gr where ...。因此，每个 DynGraph 也是一个 Graph；类型签名 f::DynGraph g => ... 允许您在类型 g 上同时使用 DynGraph 和 Graph 函数。换句话说，这不是您遇到的问题。问题是编译器无法推断类型 gr0(未声明的中间类型)是任一类的成员。

编辑:更准确地说，实际上使用类函数需要类约束或已知是类成员的特定类型。我们的函数 f 和 f' 是单态的；所有类型都已指定，GHC 应该能够生成实际的、可运行的代码。但是请记住，类函数是按类型定义的； GHC 到哪里去获取f 中的类函数(这里的术语是“类字典”)？

指定类型，如我的 f'，是一种解决方案。您还可以使函数本身多态，以一种依赖注入(inject)的方式。您至少需要 ScopedTypeVariables:

f'' :: Graph g => proxy g -> [Shape] -> [LNode Shape]
f'' _ shapes = consumeGraph (makeGraph shapes :: g)

请注意，函数的第一个参数实际上并不需要存在；它只是调用者指定 g 类型的一种机制。调用者将使用 Data.Proxy 中的 Proxy。 this SO question 中有一些关于 Proxy 的讨论。以及这里和其他地方的许多其他地方。